典型９０問 073 - We Need Both a and b（★5）

グラフDPをする

dp[i][j] =   (i=0 なら、jが所属している連結成分はaのみで出来ていて、それ以外の連結成分はaとbで出来ている

                 i=1なら、jが所属している連結成分はbのみで〜〜〜

                 i=2なら、jが所属している連結成分はaとbから〜〜〜

今見ているノードがaの時、状態の全体（i=0 or i=1 or i=2)は

子がa:

         エッジを引く　ー＞　子の状態が、i=0 or i = 1 or i = 2

         エッジを引かない　ー＞　 子の状態が、i=2　（子の状態がi=0 or i=1のときにエッジを引かないと、すべての連結成分がaとbを含むという制約を満たさない)

　　　全部でdp[0]+dp[1]+dp[2]*2

           この内、親の所属している連結成分にaのみ含まれるようになる状態は

            dp[0]  +dp[2]  (エッジを引いたときに子の状態がi=0と、引かないときのi=2)

子がb:

         エッジを引く　子の状態が、i=0 or i = 1 or i = 2

         エッジを引かない 子の状態が、i=2　（子の状態がi=0 or i=1のときにエッジを引かないと、すべての連結成分がaとbを含むという制約を満たさない)

           全部でdp[0]+dp[1]+dp[2]*2

          この内、親の所属している連結成分にaのみ含まれるようになる状態は

           dp[2] 

今見ているノードがbの時、〜〜〜

全部からaのみになるやつを引くと、aとbを含むやつが計算できる

aとbを含む奴を計算して、全体から引いてaのみを計算するようにしてみる

v0 = 今見ている部分木が、aかbどっちかしか含まないようになる or 両方含むようになる　パターン

v1 = aかbどっちかしか含まないようになる　パターン

v0-v1が i=2の答え

1. fn dfs(s:usize, bef:usize, g:&Vec<Vec<usize>>, dp:&mut Vec<Vec<usize>>, c:&Vec<char>){
2. let mut all = 1;
3. let mut v0 = 1;
4. let mut v1 = 1;
5.  
6. for i in &g[s]{
7. if *i == bef{
8. continue;
9. }
10. dfs(*i, s, g, dp, c);
11. if c[s] == 'a'{
12. if c[*i] == 'a'{
13. all*=(dp[0][*i]+dp[2][*i]*2%MODu)%MODu;
14. all%=MODu;
15. v0 *= (dp[0][*i]+dp[2][*i]*2%MODu)%MODu;
16. v0 %= MODu;
17. v1 *= (dp[0][*i]+dp[2][*i])%MODu;
18. v1 %=MODu;
19. }
20. else{
21. all*=(dp[1][*i]+dp[2][*i]*2%MODu)%MODu;
22. all%=MODu;
23. v0 *= (dp[1][*i] + dp[2][*i]*2%MODu)%MODu;
24. v0 %= MODu;
25. v1 *=dp[2][*i];
26. v1 %=MODu;
27. }
28. }
29. else{
30. if c[*i] == 'a'{
31. all*=(dp[0][*i]+dp[2][*i]*2%MODu)%MODu;
32. all%=MODu;
33. v0 *= (dp[0][*i] + dp[2][*i]*2)%MODu;
34. v0 %= MODu;
35. v1 *=dp[2][*i];
36. v1 %=MODu;
37. }
38. else{
39. all*=(dp[1][*i]+dp[2][*i]*2%MODu)%MODu;
40. all%=MODu;
41. v0 *= (dp[1][*i]+dp[2][*i]*2)%MODu;
42. v0 %= MODu;
43. v1 *= (dp[1][*i]+dp[2][*i])%MODu;
44. v1 %=MODu;
45.  
46. }
47. }
48. }

難しかった　すごく