Advertisement
Guest User

Untitled

a guest
Dec 14th, 2019
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.70 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const ll mod=998244353;
  5. #define fi first
  6. #define se second
  7. int n;
  8. ll dp[200001],dp2[200001],dp3[200001],dp4[200001];//killed dad, dad was dead, dad killed you,someone killed you before dad
  9. vector<pair<int,int> >adj[200001];
  10. void dfs(int id,int p){
  11. sort(adj[id].begin(),adj[id].end());
  12. int pw=0;
  13. for(auto cur:adj[id]){
  14. if(cur.se==p){
  15. pw=cur.fi;continue;
  16. }
  17. dfs(cur.se,id);
  18. }
  19. //case 1: killed dad
  20. ll z1=1,z2=0;
  21. for(auto cur:adj[id]){
  22. if(cur.se==p) continue;
  23. if(cur.fi<pw){
  24. z2=0;
  25. z1=(z1*(dp4[cur.se]+dp3[cur.se]))%mod;
  26. }
  27. else{
  28. z2=(z2*(dp2[cur.se])+z1*(dp[cur.se]))%mod;
  29. z1=(z1*(dp3[cur.se]+dp4[cur.se]))%mod;
  30. }
  31. }
  32. dp[id]=(z1+z2)%mod;
  33. z1=1,z2=0;
  34. for(auto cur:adj[id]){
  35. if(cur.se==p) continue;
  36. z2=(z2*(dp2[cur.se])+z1*(dp[cur.se]))%mod;
  37. z1=(z1*(dp3[cur.se]+dp4[cur.se]))%mod;
  38. }
  39. dp2[id]=(z1+z2)%mod;
  40. z1=1,z2=0;
  41. for(auto cur:adj[id]){
  42. if(cur.se==p){
  43. z2=z1;z1=0;continue;
  44. }
  45. if(cur.fi<pw){
  46. z2=0;
  47. z1=(z1*(dp4[cur.se]+dp3[cur.se]))%mod;
  48. }
  49. else z2=(z2*dp2[cur.se])%mod;
  50. }
  51. dp3[id]=z2;
  52. z1=1,z2=0;
  53. for(auto cur:adj[id]){
  54. if(cur.se==p){
  55. z1=0;continue;
  56. }
  57. if(cur.fi<pw){
  58. z2=(z2*(dp2[cur.se])+z1*(dp[cur.se]))%mod;
  59. z1=(z1*(dp3[cur.se]+dp4[cur.se]))%mod;
  60. }
  61. else z2=(z2*dp2[cur.se])%mod;
  62. }
  63. dp4[id]=z2;
  64. //cout << id << ' ' << dp[id] << ' ' << dp2[id] << ' ' << dp3[id] << ' ' << dp4[id] << endl;
  65. }
  66. int u[200001],v[200001];
  67. int main(){
  68. ios::sync_with_stdio(false);
  69. cin >> n;
  70. for(int i=1; i<n ;i++){
  71. int u,v;cin >> u >> v;
  72. adj[u].push_back({i,v});
  73. adj[v].push_back({i,u});
  74. }
  75. dfs(1,0);
  76. cout << dp2[1] << endl;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement