【动态规划】换根DP

设 (f[u]) 为以1为根时，u节点的子树中的答案。
设 (g[u]) 为以1为根时，u节点向父亲p方向看，包括父亲p但不包括u节点的子树中的答案。

则答案为 (f[u]+g[u])

当维护g的运算是一个群时，可以直接用逆运算去掉当前节点u的贡献。

void dfs1(int u, int p) {
    f[u] = 1;
    for(int &v : G[u]) {
        if(v == p)
            continue;
        dfs1(v, u);
        f[u] += f[v];
    }
}

void dfs2(int u, int p) {
    if(p == 0)
        g[u] = 0;
    int sum = 0;
    for(int &v : G[u]) {
        if(v == p)
            continue;
        sum += contribution(v);
    }
    for(int &v : G[u]) {
        if(v == p)
            continue;
        g[v] = g[u] + sum - contribution(v);
        dfs2(v, u);
    }
}

当维护的运算是不存在逆元的半群时，要用奇奇怪怪的方法计算。例如假如是要求最大值，那么就维护第1大和第2大。

struct MAX2 {

    int max1, max2;

    void Init() {
        max1 = -INF, max2 = -INF;
    }

    // Insert value v
    void Insert(int v) {
        if(v > max2) {
            max2 = v;
            if(max2 > max1)
                swap(max1, max2);
        }
    }

    // Remove value v and query max
    int RemoveMax(int v) {
        if(v == max1)
            return max2;
        return max1;
    }

};

https://codeforces.com/contest/708/problem/C

题意：给一棵树，对于每个点，问是否可以在（你自己想要怎么操作就怎么操作）一次操作之后使得删去这个点之后剩下的连通块的大小都不超过n/2。操作为删除一条边然后加上一条边，并保证操作之后仍然是一棵树。

题解：设siz[u]为以1为根时，子树的siz。设 X[u] 为 以 u 为根时，最大的子树的siz，设Y1[u] 为以 1为根时，u节点内的不超过n/2的最大的子树的siz，设 Y2[u] 为从以 1 为根换到以u为根时，从u节点方向往下看，看到p节点内的不超过n/2的最大的子树的siz。答案为X[u]<=n/2，或者以u为根时，那棵唯一的最大的子树减去其不超过n/2的最大的子树（并把这个子树直接连接到u上面）之后的siz不超过n/2。

麻烦的是Y2[u]，Y2[u]=n-siz[u]leq n/2 ? n-siz[u] : max(Y2[p],max_{vin ch[p],v eq u}Y1[v]) ，后面这个遍历p节点的子树的所有Y1[v]，然后除去Y1[u]之后的最大值，需要用上面的MAX2数据结构来维护。