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：

#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;
}