Codeforces 600E （dsu on tree）

Codeforces 600E （dsu on tree）

传送门

题意：

求以 i i i为根的子树中，出现颜色次数最多的颜色编号之和。

思路：

先考虑最暴力的解法：枚举每个节点，dfs其子树暴力求解，复杂度 O ( n 2 ) O(n^2) O(n2)
我们可以先重链剖分出每个节点的重儿子，处理轻链的答案然后合并到重儿子上，更新答案后消除轻儿子对答案的贡献，复杂度 O ( n l o g n ) O(nlogn) O(nlogn)

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<vector> 
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define mem(a,b) memset(a,b,sizeof(a));
#define lowbit(x)  x&-x;  
#define debugint(name,x) printf("%s: %dn",name,x);
#define debugstring(name,x) printf("%s: %sn",name,x);
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-6;
const int maxn = 1e5+5;
const ll mod = 1e9+7;
inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}vector<int>g[maxn];
ll kind[maxn],ans[maxn],n,mx,sum,col[maxn],son[maxn],sz[maxn],wson;
void dfs(int u,int fa){  //重链剖分 sz[u] = 1;for(auto v:g[u]){if(v == fa) continue;dfs(v,u);sz[u] += sz[v];if(sz[v] > sz[son[u]]){son[u] = v;}}
}
void solve(int u,int fa,int val){kind[col[u]] += val;if(kind[col[u]] > mx){mx = kind[col[u]];sum = col[u];}else if(kind[col[u]] == mx){sum += col[u];}for(auto v:g[u]){if(v == fa || v == wson) continue;solve(v,u,val);}}
void dfsans(int u,int fa,int opt){ //opt表示是否要消除贡献 for(auto v:g[u]){if(v == fa) continue;//dfsans(v,u,opt);if(v != son[u]){dfsans(v,u,0);  //处理轻链 }}if(son[u]){dfsans(son[u],u,1); //处理重链wson = son[u];}solve(u,fa,1);  //处理轻链的答案 wson = 0;ans[u] = sum;if(!opt) solve(u,fa,-1),mx = 0,sum = 0; //消除当前节点轻链的贡献 }
int main(){scanf("%d",&n);for(int i = 1; i <= n; i++)scanf("%lld",&col[i]);for(int i = 1; i < n; i++){int u,v;scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}dfs(1,0);dfsans(1,0,0);for(int i = 1; i <= n; i++)printf("%lld ",ans[i]);}