bzoj5457 城市

一棵树，每个点有一个民族，和一个人数，求每个子树里最多的民族及其人数，如果一样，输出编号最小的

$n \leq 500000$

sol：

卡莫队的毒瘤题，需要 dsu on tree

大概就是 dfs 顺便维护一个数组叫“当前答案”，每次先把轻儿子加进来，再把重儿子加进来，然后把轻儿子删掉，重儿子继承这个“当前答案”数组

然后由于两点间最多有 log 条重链，复杂度很对劲

#include <bits/stdc++.h>

#define LL long long

#define rep(i, s, t) for (register int i = (s), i##end = (t); i <= i##end; ++i)

#define dwn(i, s, t) for (register int i = (s), i##end = (t); i >= i##end; --i)

using namespace std;

inline int read() {

    int x = , f = ; char ch;

    for (ch = getchar(); !isdigit(ch); ch = getchar()) if (ch == '-') f = -f;

    for (; isdigit(ch); ch = getchar()) x =  * x + ch - '';

    return x * f;

}

const int maxn = ;

int n, m, a[maxn], b[maxn];

int first[maxn], to[maxn << ], nx[maxn << ], pnt;

inline void add(int u, int v) {

    to[++pnt] = v;

    nx[pnt] = first[u];

    first[u] = pnt;

}

int fa[maxn], mxs[maxn], size[maxn];

inline void dfs1(int x) {

    size[x] = ;

    for(int i=first[x];i;i=nx[i]) {

        if(to[i] == fa[x]) continue;

        fa[to[i]] = x;

        dfs1(to[i]); size[x] += size[to[i]];

        if(size[to[i]] > size[mxs[x]]) mxs[x] = to[i];

    }

}

int cnt[maxn], now;

int ans[maxn], ansn[maxn];

inline void cal(int x, int opt) {

    cnt[b[x]] += opt * a[x];

    if((cnt[b[x]] > cnt[now]) || ((cnt[b[x]] == cnt[now]) && (b[x] < now) && (opt == ))) now = b[x];

    for(int i=first[x];i;i=nx[i])

        if(to[i] != fa[x]) cal(to[i], opt);

}

inline void dfs(int x, int opt) {

    for(int i=first[x];i;i=nx[i])

        if(to[i] != fa[x] && to[i] != mxs[x]) dfs(to[i], );

    if(mxs[x]) dfs(mxs[x], );

    for(int i=first[x];i;i=nx[i])

        if(to[i] != fa[x] && to[i] != mxs[x]) cal(to[i], );

    cnt[b[x]] += a[x];

    if((cnt[b[x]] > cnt[now]) || ((cnt[b[x]] == cnt[now]) && (b[x] < now))) now = b[x];

    ans[x] = now; ansn[x] = cnt[now];

    if(!opt) now = , cal(x, -);

}

int main() {

    n = read(), m = read();

    rep(i, , n) {

        int u = read(), v = read();

        add(u, v); add(v, u);

    } dfs1(); cnt[] = -;

    rep(i, , n) b[i] = read(), a[i] = read();

    dfs(, );

    rep(i, , n) printf("%d %d\n", ans[i], ansn[i]);

}