2020CCPC长春题解 I - Kawaii Courier

题目大意：给一个树，让你求每个节点走到根节点的期望的d*x^d，d为走过的边个数。走法是每次随机等概率走到相邻的点。

题目分析：　相对于经典的距离d的期望，这里要求的是d*x^d的期望。

　　　　　　我们设F(a)=a *x^a

　　　　　　考察F(a+b)与F(a) F(b)的关系，很遗憾，没法直接表示。

　　　　　　引入，辅助函数G(a)=x^a

　　　　　　那么F（a+b)=F(a)*G(b)+F(b)*G(a)

　　　　　　而G(a+b)=G(a)*G(b)

　　　　　　那么分别用两个DFS求出F，G。再用一个DFS得到答案即可。复杂度O（nlogn) n是dfs复杂度，log是逆元复杂度。
代码如下：

 1 #include <bits/stdc++.h>

 2 using namespace std;

 3 const long long mod=1e9+7;

 4 const long long maxn=1e5+10;

 5 long long b[maxn],c[maxn],n,k,px,qx,nx,u,v,ans;

 6 vector<long long> a[2*maxn];

 7 long long ksm(long long x,long long t)

 8 {

 9     long long ans=1;

10     long long res=x;

11     while (t)

12     {

13         if (t&1) ans=ans*res%mod;

14         res=res*res%mod;

15         t=t>>1;

16     }

17     return ans;

18 }

19 long long _inv(long long x)

20 {

21     x=(x%mod+mod)%mod;

22     return ksm(x,mod-2);

23 }

24 void init()

25 {

26     scanf("%lld%lld%lld%lld",&n,&k,&px,&qx);

27     nx=(px*ksm(qx,mod-2))%mod;

28     for (int i=1;i<n;i++)

29     {

30         scanf("%lld%lld",&u,&v);

31         a[u].push_back(v);

32         a[v].push_back(u);

33     }

34 }

35 void dfs1(long long x,long long fa)

36 {

37     long long sum=0;

38     for (int i=0;i<a[x].size();i++)

39     {

40         if (a[x][i]==fa) continue;

41         dfs1(a[x][i],x);

42         sum=(sum+b[a[x][i]])%mod;

43     }

44     b[x]=(nx*_inv(a[x].size()-nx*sum%mod))%mod;

45 }

46 void dfs2(long long x,long long fa)

47 {

48     long long sum1=0,sum2=0;

49     for (int i=0;i<a[x].size();i++)

50     {

51         if (a[x][i]==fa) continue;

52         dfs2(a[x][i],x);

53         sum1=(sum1+b[a[x][i]])%mod;

54         sum2=(sum2+c[a[x][i]])%mod;

55     }

56     c[x]=((nx*b[x]%mod)*(sum1+sum2)%mod+nx)%mod;

57     c[x]=c[x]*_inv(a[x].size()-nx*sum1%mod)%mod;

58 }

59 void get_ans(long long x,long long fa,long long f,long long g)

60 {

61     if (x!=k)     ans=ans^(x*((f*c[x]+g*b[x])%mod)%mod);

62     for (int i=0;i<a[x].size();i++)

63     {

64         if (a[x][i]==fa) continue;

65         get_ans(a[x][i],x,f*b[x]%mod,(f*c[x]+g*b[x])%mod);

66     }

67 }

68 int main()

69 {

70     init();

71     dfs1(k,k);

72     dfs2(k,k);

73     b[k]=1;

74     c[k]=0;

75     ans=0;

76     get_ans(k,k,1,0);

77     printf("%lld\n",ans);

78     return 0;

79 }

of I

巴特西

2020CCPC长春题解 I - Kawaii Courier

最新文章

热门文章