Codeforces 600E. Lomsat gelral

学习了一下dsu on tree

所以为啥是dsu而不是dfs on tree？？？

这道题先把这棵树轻重链剖分了，然后先处理轻儿子，处理完轻儿子后要把轻儿子的贡献都给删了

然后为了计算这个点的贡献，我把所有轻儿子的贡献加回来

如果这个点是个轻儿子，没什么人权，我就再遍历整棵树把它清空

其实我希望的是把整个数组清空，又不能一个一个清，所以把当前子树遍历一遍清空

唔，感觉说的好短，但是确实是这样的……

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 100005

#define ba 47

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 +c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

struct node {

    int to,next;

}E[MAXN * 2];

int head[MAXN],sumE;

int N,c[MAXN],siz[MAXN],son[MAXN];

int val[MAXN],mval;

int64 sum,ans[MAXN];

bool vis[MAXN];

void add(int u,int v) {

    E[++sumE].to = v;

    E[sumE].next = head[u];

    head[u] = sumE;

}

void dfs(int u,int fa) {

    siz[u] = 1;

    for(int i = head[u] ; i ; i = E[i].next) {

	int v = E[i].to;

	if(v != fa) {

	    dfs(v,u);

	    siz[u] += siz[v];

	    if(siz[v] > siz[son[u]]) son[u] = v;

	}

    }

}

void change(int u,int fa,int k) {

    val[c[u]] += k;

    if(k == -1) vis[u] = 0;

    if(val[c[u]] >= mval) {

	if(val[c[u]] > mval) {mval = val[c[u]];sum = 0;}

	sum += c[u];

    }

    for(int i = head[u] ; i ; i = E[i].next) {

	int v = E[i].to;

	if(v != fa && (!vis[v] || k == -1)) {

	    change(v,u,k);

	}

    }

}

void calc(int u,int fa,bool f) {

    for(int i = head[u] ; i ; i = E[i].next) {

	int v = E[i].to;

	if(v != fa && v != son[u]) {

	    calc(v,u,0);

	}

    }

    if(son[u]) {calc(son[u],u,1);vis[son[u]] = 1;}

    change(u,fa,1);

    ans[u] = sum;

    if(!f) {change(u,fa,-1);sum = 0;mval = 0;}

}

void Solve() {

    read(N);

    for(int i = 1 ; i <= N ; ++i) read(c[i]);

    int a,b;

    for(int i = 1 ; i < N ; ++i) {

	read(a);read(b);

	add(a,b);add(b,a);

    }

    dfs(1,0);

    calc(1,0,1);

    for(int i = 1 ; i <= N ; ++i) {

	out(ans[i]);space;

    }

    enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

}