牛客练习赛142-D.第四次忍界大战（会被误认为树上dp）（先计算，后合并）（点分治） · znzryb
## 思路讲解
那么根据我的经验来说，如果说这个东西要求连续性（如距离，字母排列等等），大概率是树上dp，像这种具有超距作用的，那么大概率就是要配合DSU了。
核心代码如下，注意，**先计算，后合并**。
```cpp
FOR(i,1,N){ // 特判两个点的情况
for(auto &v:g[i]){
if(A[v]==A[i]) ++ans;
}
}
// 生成的这张图相当于其权值都是大于等于key的（至少是相连的图，孤立点我们不知道）
// 这个时候就是要看两个相同的A值点，是不是连接于这个图上面。
// 那么我们发现不用把问题想的非常复杂，只需要考虑key-1（即后面一个k）就行了
// 最重要的是遵循"先计数，后合并"的原则
for(auto it=mp.rbegin();it!=mp.rend();it++){
// auto& 相当于定义了一个别名
auto& ls=it->second;ll key=it->first;
map<ll,ll> cnt;
// 先计数
for(auto &u:ls){
vector<ll> wp;
for(auto &v:g[u]){
if(A[v]<=key) continue;
wp.pb(find(v));
}
wp.resize(unique(all(wp))-wp.begin());
for(auto &v:wp){
++cnt[find(v)];
}
}
for(auto &t:cnt){
ll n=t.second;
ans+=(n-1+1)*(n-1); // 2Cn * 2 在n个中选两个，然后由于先选哪个比较重要*2
}
// 后合并
for(auto &u:ls){
for(auto &v:g[u]){
if(A[v]<key) continue;
merge(u,v);
}
}
}
```
那么这种复杂路径问题，点分治也能解决（应该来说更泛用）。
## AC代码
[https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78161052](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78161052)
::: 源代码（并查集）
```cpp
// Problem: 第四次忍界大战
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/112575/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
using namespace std;
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(1e5)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll MAXM=(ll)1e6+10;constexpr ll MAXV=(ll)1e6+10;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT,A[MAXN];
/*
*/
map<ll, vector<ll > > mp;
bool cmp(const arr2 &a,const arr2 &b){
return min(a[0],a[1])<min(b[0],b[1]);
}
ll fa[MAXN];
ll find(ll x){
if(x==fa[x]) return fa[x];
return fa[x]=find(fa[x]);
}
void merge(ll a,ll b){
fa[find(a)]=find(b);
}
vector<ll> g[MAXN]; // 记得要清空
inline void solve(){
cin>>N;
FOR(i,1,N){
fa[i]=i;
}
FOR(i,1,N){
cin>>A[i];
mp[A[i]].pb(i);
}
// map<ll, vector<arr2> > E;
FOR(i,1,N-1){
ll u,v;
cin>>u>>v;
// E[min(A[u],A[v])].pb({u,v});
g[u].pb(v);g[v].pb(u);
}
ll ans=0;
FOR(i,1,N){ // 特判两个点的情况
for(auto &v:g[i]){
if(A[v]==A[i]) ++ans;
}
}
// 生成的这张图相当于其权值都是大于等于key的（至少是相连的图，孤立点我们不知道）
// 这个时候就是要看两个相同的A值点，是不是连接于这个图上面。
// 那么我们发现不用把问题想的非常复杂，只需要考虑key-1（即后面一个k）就行了
// 最重要的是遵循"先计数，后合并"的原则
for(auto it=mp.rbegin();it!=mp.rend();it++){
// auto& 相当于定义了一个别名
auto& ls=it->second;ll key=it->first;
map<ll,ll> cnt;
// 先计数
for(auto &u:ls){
vector<ll> wp;
for(auto &v:g[u]){
if(A[v]<=key) continue;
wp.pb(find(v));
}
wp.resize(unique(all(wp))-wp.begin());
for(auto &v:wp){
++cnt[find(v)];
}
}
for(auto &t:cnt){
ll n=t.second;
ans+=(n-1+1)*(n-1); // 2Cn * 2 在n个中选两个，然后由于先选哪个比较重要*2
}
// 后合并
for(auto &u:ls){
for(auto &v:g[u]){
if(A[v]<key) continue;
merge(u,v);
}
}
}
cout<<ans<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// cin>>lT;
// while(lT--)
solve();
return 0;
}
/*
96% https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78160882
AC https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78161052
*/
```
:::
[https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78175127](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78175127)
::: 源代码（点分治）
```cpp
// Problem: 第四次忍界大战
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/112575/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
using namespace std;
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll MAXM=(ll)1e6+10;constexpr ll MAXV=(ll)1e5+10;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT,A[MAXN];
/*
*/
inline void solve(){
cin>>N;
vector<vector<ll> > g(N+5);
FOR(i,1,N){
cin>>A[i];
}
FOR(i,1,N-1){
ll u,v;
cin>>u>>v;
g[u].pb(v);g[v].pb(u);
}
vector<ll> sz(N+5,0);ll mxTree=INF;
vector<bool> vis(N+5,0);ll root=0;
ll ans=0;
// FOR(i,1,N){ // 特判两个点的情况
// for(auto &v:g[i]){
// if(A[v]==A[i]) ++ans;
// }
// }
// ans/=2;
// #ifdef LOCAL
// debug(ans);
// #endif
auto get=[&](auto &&self,ll u,ll p,ll tot)->void{
ll val=0;sz[u]=1;
for(auto &v:g[u]){
if(v==p || vis[v]) continue;
self(self,v,u,tot);
sz[u]+=sz[v];
val=max(val,sz[v]);
}
val=max(val,tot-sz[u]);
if(val<mxTree){
mxTree=val;
root=u;
}
};
auto cal=[&](ll u)->void{
map<ll,ll> cnt;vector<ll> wp;
// 那么众所周知，我们只考虑经过u的路径（点分治）
auto dfs=[&](auto &&self,ll u,ll p,ll mn)->void{
if(mn>A[u]){
// if(cnt.count(A[u])){
// ans+=cnt[A[u]];
// }
// ++cnt[A[u]];
wp.pb(A[u]);
}
mn=min(A[u],mn);
for(auto &v:g[u]){
if(v==p || vis[v]) continue;
self(self,v,u,mn);
}
};
#ifdef LOCAL
debug(root);
debug(ans);
#endif
// 保证计入答案的路径是经过u点的
for(auto &v:g[u]){
if(vis[v]) continue; // 你不能就不判断了
dfs(dfs,v,u,INF);
// #ifdef LOCAL
// if(root==1){
// for(auto &a:wp){
// debug(a);
// }
// debug(ans);
// }
// #endif
for(auto &a:wp){
// 跨区域合并不行，因为根节点值太低了
if(a>=A[u]) continue;
if(cnt.count(a)){
ans+=cnt[a];
}
}
for(auto &a:wp){
++cnt[a];
}
wp.clear();
}
// 根节点直接和子树上的点匹配
ans+=cnt[A[u]];
#ifdef LOCAL
debug(ans);
#endif
};
// 主程序
auto dfz=[&](auto &&self,ll u)->void{
vis[u]=true; // u一定是一个重心
cal(u);
for(auto &v:g[u]){
if(vis[v]) continue;
mxTree=INF;
get(get,v,u,sz[v]);
// #ifdef LOCAL
// debug(root);
// #endif
self(self,root);
}
};
get(get,1,1,N);
#ifdef LOCAL
debug(root);
#endif
dfz(dfz,root);
ans*=2; // 该路径是考虑顺序的
cout<<ans<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// cin>>lT;
// while(lT--)
solve();
return 0;
}
/*
WA 60% https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78164958
hack:
10
4 4 5 3 2 5 4 4 5 5
5 10
1 3
5 6
4 6
9 2
1 7
8 9
2 3
10 7
ans:
6
AC https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78175127
*/
```
:::
## 心路历程（WA，TLE，MLE……）
WA了的点分治代码，过了60%，我认为错误就在这个我的这个点分治统计答案他有点问题，统计到的不一定都经过u，这是违背点分治思想的。
[https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78164958](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78164958)
::: 源代码（点分治）
```cpp
// Problem: 第四次忍界大战
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/112575/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
using namespace std;
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll MAXM=(ll)1e6+10;constexpr ll MAXV=(ll)1e5+10;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT,A[MAXN];
/*
*/
inline void solve(){
cin>>N;
vector<vector<ll> > g(N+5);
FOR(i,1,N){
cin>>A[i];
}
FOR(i,1,N-1){
ll u,v;
cin>>u>>v;
g[u].pb(v);g[v].pb(u);
}
vector<ll> sz(N+5,0);ll mxTree=INF;
vector<bool> vis(N+5,0);ll root=0;
ll ans=0;
FOR(i,1,N){ // 特判两个点的情况
for(auto &v:g[i]){
if(A[v]==A[i]) ++ans;
}
}
ans/=2;
auto get=[&](auto &&self,ll u,ll p,ll tot)->void{
ll val=0;sz[u]=1;
for(auto &v:g[u]){
if(v==p || vis[v]) continue;
self(self,v,u,tot);
sz[u]+=sz[v];
val=max(val,sz[v]);
}
val=max(val,tot-sz[u]);
if(val<mxTree){
mxTree=val;
root=u;
}
};
auto cal=[&](ll u)->void{
map<ll,ll> cnt;
// 那么众所周知，我们只考虑经过u的路径（点分治）
auto dfs=[&](auto &&self,ll u,ll p,ll mn)->void{
if(mn>A[u]){
if(cnt.count(A[u])){
ans+=cnt[A[u]];
}
++cnt[A[u]];
}
mn=min(A[u],mn);
for(auto &v:g[u]){
if(v==p || vis[v]) continue;
self(self,v,u,mn);
}
};
dfs(dfs,u,u,INF);
};
// 主程序
auto dfz=[&](auto &&self,ll u)->void{
vis[u]=true; // u一定是一个重心
cal(u);
for(auto &v:g[u]){
if(vis[v]) continue;
mxTree=INF;
get(get,v,v,sz[v]);
self(self,root);
}
};
get(get,1,1,N);
dfz(dfz,root);
ans*=2; // 该路径是考虑顺序的
cout<<ans<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// cin>>lT;
// while(lT--)
solve();
return 0;
}
/*
*/
```
:::
[https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78165041](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78165041)
然后改了统计代码以后WA的更多了
[https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78165092](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78165092)
AI指出了一个不对的地方，现在正确率提升到了84%
```cpp
// 保证计入答案的路径是经过u点的
for(auto &v:g[u]){
if(vis[v]) continue; // 你不能就不判断了
dfs(dfs,v,u,A[u]);
for(auto &a:wp){
if(cnt.count(a)){
ans+=cnt[a];
}
}
for(auto &a:wp){
++cnt[a];
}
wp.clear();
}
```