【日常小测】spread

  • 本文为博主原创,未经许可不得转载

分析:设f[x]表示x为根子树的答案,考虑每个儿子可以选也可以不选

那么儿子y的贡献就是f[y]+1

这样dp一遍可以求出根节点的答案

然后再dp一遍乘上父亲的贡献,就能求出所有点为根的答案

考试时脑残了,没有去掉clock(),好惨啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 100100
using namespace std;
const int mod=1e9+7;
struct node{int y,next;}e[MAXN<<1];
int n,len,Link[MAXN],f[MAXN];
inline int read(){
int x=0,f=1; char ch=getchar();
while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
inline int sub(int a,int b){return (a-=b)<0?a+mod:a;}
inline int mul(int a,int b){return 1LL*a*b%mod;}
inline int fast(int a,int b){int ret(1);for(;b;b>>=1,a=mul(a,a))if(b&1)ret=mul(ret,a);return ret;}
inline int Ni(int a){return fast(a,mod-2);}
void insert(int x,int y){e[++len].next=Link[x];Link[x]=len;e[len].y=y;}
void dfs1(int x,int fa){
f[x]=1;
for(int i=Link[x];i;i=e[i].next)if(e[i].y!=fa){
dfs1(e[i].y,x);
f[x]=mul(f[x],add(f[e[i].y],1));
}
}
void dfs2(int x,int fa){
for(int i=Link[x];i;i=e[i].next)if(e[i].y!=fa){
f[e[i].y]=mul(f[e[i].y],add(mul(f[x],Ni(add(f[e[i].y],1))),1));
dfs2(e[i].y,x);
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
n=read();
for(int i=1;i<n;++i){
int x=read(),y=read();
insert(x,y); insert(y,x);
}
dfs1(1,0);
dfs2(1,0);
for(int i=1;i<=n;++i) printf("%d ",f[i]); printf("\n");
return 0;
}
文章目录
,