Develop a Tree 题解

 ~~感觉太板了~~。 ## subtask 1 考虑二分图的性质： > 二分图不存在长度为奇数的环。 由于加边后树变为基环树，有且只有一个环。易得对答案有贡献的点，距离只能为奇数，这样才可以保证产生的环长为偶数。 记 $d(X,Y)$ 为 $X$ 和 $Y$ 之间的距离，$R$ 为根节点，$L$ 当前两个节点的 LCA。 根据 LCA，两个点的距离为： $$d(X,Y)=d(x,R)+d(y,R)-2d(L,R)$$ 然而本题中仅需要求路径长度的奇偶性，所以有： $$d(X,Y)\equiv(x,R)+d(y,R)(\operatorname{mod} 2)$$ 得出结论： > 两个点距离为奇数，当且仅当其到根节点距离和为奇数。 又根据小学数学，只有奇数加偶数为奇数，即： > 两个点距离为奇数，当且仅当其中一个点到根节点距离为偶数，而另一个节点到根节点距离为奇数。 所以这个题实际上是求：在 $i$ 的子树中到 $i$ 距离为偶数（奇数）的点的数量，乘积即为 $f(i,1)$。 考虑 dfs 的同时维护一个 dp 数组，其中 $dp_{i,x}$ 表示 $i$ 的子树中到 $i$ 的距离模 $2$ 为 $x$ 的点的个数。 有转移式（令 $v$ 为 $u$ 的儿子）： $$dp_{u,0}=\sum dp_{v,1}+1$$ $$dp_{u,1}=\sum dp_{v,0}$$ 输出 $f(i,1)=dp_{i,0}\times dp_{i,1}$ 即可。复杂度 $O(n)$。 ## subtask 2 可以直接枚举每个点对，计算距离。但是问题在于 $k>1$。 不难发现添加 $k$ 条边等价于在可添加的边里选 $k$ 条。所以 $f(i,k)=C_{f(i,1)}^{k}$。 由于模数是质数，可以直接 $O(k)$ 求组合数。 ## subtask 3,4 将 subtask1 和 subtask2 的做法结合起来即可，时间复杂度 $O(\sum k\log_2p_i)=O(nk\log p)$，TLE。 所以考虑优化掉 $\log$，显然可以开个桶预处理逆元，于是就做完了。 std by caosheng_zzz： ```cpp #include <algorithm> #include <iostream> #include <string.h> #include <stdio.h> #include <math.h> #include <queue> #include <map> #include <set> typedef int intt ; #define prt printf #define ll long long #define int __int128 #define spc prt(" ") #define ent prt("\n") #define pr_ prt("---") #define prx prt("***") using namespace std; int read(){ int f = 1 , k = 0; char c = getchar(); while(c < '0' || c > '9'){ if(c == '-') f = -1; c = getchar() ; } while(c >= '0' && c <= '9'){ k = (k << 3) + (k << 1) + (c ^ 48); c = getchar() ; } return (f == 1 ? k : -k); } void output(int now){ if(now < 0){ putchar('-'); output(- now); } else{ if(now > 9) output(now / 10); putchar((now % 10) ^ 48); } } const intt maxn = 5e5 + 1; const ll Mod[] = {0 , 999998003 , 999998017 , 999998023 , 999998059 , 999998081 , 999998107 , 999998119 , 999998137 , 999998141 , 999998143 , 999998147 , 999998173 , 999998183 , 999998203 , 999998243 , 999998261 , 999998269 , 999998309 , 999998339 , 999998369 , 999998423 , 999998459 , 999998501 , 999998507 , 999998509 , 999998533 , 999998537 , 999998563 , 999998609 , 999998617 , 999998621 , 999998627 , 999998639 , 999998641 , 999998653 , 999998663 , 999998683 , 999998687 , 999998689 , 999998693 , 999998777 , 999998789 , 999998801 , 999998843 , 999998863 , 999998869 , 999998903 , 999998917 , 999998921 , 999998929 , 999998957 , 999998959 , 999998971 , 999998981 , 999999001 , 999999017 , 999999029 , 999999043 , 999999059 , 999999067 , 999999103 , 999999107 , 999999113 , 999999131 , 999999137 , 999999151 , 999999163 , 999999181 , 999999191 , 999999193 , 999999197 , 999999223 , 999999229 , 999999323 , 999999337 , 999999353 , 999999391 , 999999433 , 999999487 , 999999491 , 999999503 , 999999527 , 999999541 , 999999587 , 999999599 , 999999607 , 999999613 , 999999667 , 999999677 , 999999733 , 999999739 , 999999751 , 999999757 , 999999761 , 999999797 , 999999883 , 999999893 , 999999929 , 999999937}; intt cnt = 0 , h[maxn] ; intt f[maxn][2]; struct Edge{ intt next , to; }edge[maxn << 1]; map<ll , intt> G ; ll g[100][21] , mul[100][21]; intt cour = 0 ; void add(intt u , intt v){ edge[++ cnt] = {h[u] , v}; h[u] = cnt; } void dfs(intt u , intt fa , intt deep){ f[u][deep % 2] ++ ; // output(u) , spc , output(fa) , spc , output(deep) , ent; for(intt i=h[u] ; i ; i=edge[i].next){ intt v = edge[i].to ; // output(u) , spc , output(v) , ent; if(v == fa) continue ; dfs(v , u , deep + 1) ; f[u][0] += f[v][0] , f[u][1] += f[v][1]; } return ; } int power(int base , ll s , ll p){ int res = 1; while(s){ if(s & 1) res = res * base % p; base = base * base % p; s >>= 1; } return res; } ll C(intt a , int b , ll p){ int res = 1 ; intt num = G[p]; if(b == 0 || a == 0) return 0 ; if(a > b) return 0 ; if(a == 1) return b % p ; if(a >= p) return 0 ; for(int i=1 ; i<=a ; i++){ res = res * (b - i + 1) % p * mul[num][i] % p; } return res; } signed main(){ // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n = read() , k = read() ; for(int i=1 ; i<=100 ; i++) { G[Mod[i]] = i ; for(int j=1 ; j<=k ; j++) mul[i][j] = power(j , Mod[i] - 2 , Mod[i]) ;} for(int i=1 ; i<n ; i++){ intt u , v ; cin >> u >> v ; add(u , v) , add(v, u); } dfs(1 , 0 , 1); for(int i=1 ; i<=n ; i++) { output(C(k , (__int128)f[i][0] * f[i][1] , read())) , i == n ? ent : spc ;} return 0; } ``` - 这个题所有人都认为不应该放 T4，但是最后还是放了。 - 题太水请见谅。 - 感谢阅读！