P8973 『GROI-R1』继续深潜，为了同一个梦想

P8973 『GROI-R1』继续深潜，为了同一个梦想 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P8973 『GROI-R1』继续深潜，为了同一个梦想

题目大意

我称一棵树上的一个点集是“连接的”，当且仅当树上存在一条链能够覆盖这个点集并且这个集合大小不小于 2

对于每个点，询问每个点被多少个这样的点集所包含

设 \(ans_i\) 为包含 \(i\) 号节点的连接的集合的个数对 \(10^9+7\) 取模后的值

输出 \(xor_{i = 1}^n ans_i * i\)

思路

换根 \(dp\)

设 \(f_r(x)\) 为以 \(r\) 为根时，以 \(x\) 为一个端点，在 \(x\) 的子树里面选 \(\ge1\) 个点，满足这些点在同一条链上面的方案数。

那么：

\[f_r(x) = \sum_{u\in son(x)} f_r(u) * 2 + 1 \]

因为 \(u\) 点可以选也可以不选，并且可以选 \(\{u , x\}\) 。

我算出所有 \(f\) 后考虑以 \(r\) 为根时的答案 \(ans_r\) ，设 \(g_r(u) = f_r(u) * 2 + 1\)

其实就是 \(f_r(r)\) 加上两条链连起来的总和。

那么：

\[ans_r = \sum_{u , v \in son(r) , u \neq v} g_r(u) * g_r(v) + \sum _{u \in son(r)} g_r(u) \]

设 \(s_r = \sum_{u \in son(r)} g_r(u)\)

那么：

\[ans_r = \sum_{u\in son(r)} g_r(u) * (s_r - g_r(u) + 1) \]

实现的时候两条链组成一条新的链时不要多加了

接下来考虑换根， \(u\to v\) 换根，考虑 \(f\) 的变化

\[f_v(u) =f_u(u) - (f_u(v) * 2 + 1) \newline f_v(v) = f_u(v) +f_v(u) * 2 +1 \]

其他的点 \(x\) 就是 \(f_v(x) = f_u(x)\)

code

#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define LL long long
using namespace std;
const int N = 5e5 + 5;
const LL mod = 1e9 + 7;
int hd[N] , cnt , n , fa[N];
LL f[N] , ans[N];
struct E {
    int to , nt;
} e[N << 1];
void add (int x , int y) { e[++cnt].to = y , e[cnt].nt = hd[x] , hd[x] = cnt; }
void dfs1 (int x) {
    int y;
    for (int i = hd[x] ; i ; i = e[i].nt) {
        y = e[i].to;
        if (y == fa[x]) continue;
        fa[y] = x;
        dfs1 (y);
        f[x] = (f[x] + f[y] * 2 % mod + 1) % mod;
    }
}
void dfs2 (int x) {
    int y;
    LL sum = 0;
    for (int i = hd[x] ; i ; i = e[i].nt) {
        y = e[i].to;
        sum = (sum + 2 * f[y] % mod + 1) % mod;
    }
    LL g;
    for (int i = hd[x] ; i ; i = e[i].nt) {
        y = e[i].to;
        g = (f[y] * 2 % mod + 1) % mod;
        ans[x] = (ans[x] + g * ((sum - g + mod + 1) % mod) % mod) % mod;
        sum = (sum - g + mod) % mod;
    }
    LL xx , yy;
    for (int i = hd[x] ; i ; i = e[i].nt) {
        y = e[i].to;
        if (y == fa[x]) continue;
        xx = f[x] , yy = f[y];
        f[x] = (xx + mod - (yy * 2 % mod + 1) % mod) % mod;
        f[y] = (yy + f[x] * 2 % mod + 1) % mod;
        dfs2 (y);
        f[x] = xx , f[y] = yy;
    }
}
int main () {
    int u , v;
    scanf ("%d" , &n);
    fu (i , 1 , n - 1) {
        scanf ("%d%d" , &u , &v);
        add (u , v) , add (v , u);
    }
    dfs1 (1);
    dfs2 (1);
    LL ans1 = ans[1] * 1;
    fu (i , 2 , n) ans1 = ans1 ^ (ans[i] * i);
    printf ("%lld" , ans1);
    return 0;
}