https://ac.nowcoder.com/acm/contest/11168

C. CCA的子树【树形dp】
题意：
给定一棵 n 个点的带点权的有根树，根节点为 1 。
要选出两个节点，满足任意一个不是另一个的祖先节点，最大化以两个节点为根的子树的点权和 。
如果选不出两棵合法的子树，则输出“Error”。
思路：root保存当前这个点的子树的点权和， dp表示当前这个节点及其子树中最大的点权和。 dfs的时候先处理子树， 然后用d1,d2表示当前点的子树中最大、次大的dp值， 那么当前点的dp值就是max(d1 + d2, root[u])
统计d1, d2的时候实时更新ans即可。

#include<bits/stdc++.h>
#define ll long long 
using namespace std;

const int N = 200010, M = 2 * N;

int idx, e[M], ne[M], h[N], w[M], maxdep, n;
ll dp[N], root[N], ans, dep[N];

void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++;}

void dfs(int u, int fa, int depth){
    dep[u] = depth, root[u] = w[u];
    maxdep = max(maxdep, depth);
    ll d1 = 0, d2 = 0;
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if(j == fa)    continue;
        dfs(j, u, depth + 1);
        root[u] += root[j];
        if(dp[j] >= d1)    d2 = d1, d1 = dp[j];
        else if(dp[j] > d2)    d2 = dp[j];
        dp[u] = max(dp[u], d1);
    }
    dp[u] = max(dp[u], root[u]);
    ans = max(ans, d1 + d2);
}

int main(){
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; ++ i)    scanf("%d", &w[i]);
    for(int i = 1; i <= n - 1; ++ i){
        int a, b;
        scanf("%d%d", &a,&b);
        add(a, b), add(b, a);
    }
    dfs(1, 1, 1);
    if(maxdep == n)    cout << "Error";
    else    cout << ans;    
    return 0;
}

D. CCA的小球【组合数学 容斥原理】
题意：
给定 n 个小球，每个小球有颜色，要将它们摆成一行 。
两个方案不同，当且仅当存在某个位置，两种方案摆在这个位置的小球颜色不同。
一个方案合法， 当且仅当不存在任意两个位置相邻的小球颜色相同，求合法方案数对 10^9+7 取模后的值 。
n <= 10^6，0 < 颜色编号 < 2^31，每种颜色出现次数 <= 2
思路： 因为每种颜色只有2个球， 所以可以采用捆绑法，然后用容斥原理处理：减掉只有1对颜色相同小球相邻的情况； 加上有2对颜色相同小球相邻的情况…… 注意我们一开始算的时候， 认为小球是有区别的， 所以都按A来算， 最后再除k（相同颜色对数）的阶乘即可。

#include<bits/stdc++.h>
#define ll long long 
using namespace std;

const int N = 1000010, mod = 1e9 + 7;

int n,cnt,fact[N],k,inv[N];

ll ksm(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1)    res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

ll C(int n, int m){
    return (ll)fact[n] * inv[n - m] % mod * inv[m] % mod;
}

void init(int n){
    fact[0] = 1;
    for(int i = 1; i <= n - 1; ++ i)    fact[i] = (ll)fact[i - 1] * i % mod;
    inv[n - 1] = ksm(fact[n - 1], mod - 2);
    for(int i = n - 2; i >= 0; -- i)    inv[i] = (ll)inv[i + 1] * (i + 1) % mod; 
}

int main(){
    init(1e6 + 5);
    scanf("%d",&n);
    unordered_map<int, int> mp;
    for(int i = 1; i <= n; ++ i){
        int col;
        scanf("%d", &col);
        if(mp.count(col))    k ++;        //有k个小球重复 
        else    mp[col] = 1;
    }    
    ll ans = fact[n], tmp = 1;
    for(int i = 1; i <= k; ++ i){
        tmp = tmp * 2 % mod;
        if(i & 1)    ans -= C(k, i) * fact[n - i] % mod * tmp % mod;
        else    ans += C(k, i) * fact[n - i] % mod * tmp % mod;
        ans = (ans + mod) % mod;
    }    
    ans = ans * ksm(tmp, mod - 2) % mod;
    printf("%lld", ans);
    return 0;
}