Facebook
From amsen, 11 Months ago, written in C++.
Embed
Download Paste or View Raw
Hits: 95
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7.  
  8. const int N = 2e5+100;
  9.  
  10. vector<int> g[N];
  11. int n;
  12. bool dp_dn[N][2];
  13.  
  14. map<ii, int> mp;
  15.  
  16. void fil(vector<int> &d, function<int(int, int)> f, int def){
  17.     int ls=def;
  18.     for(auto &i : d){
  19.         i = f(ls, i);
  20.         ls = i;
  21.     }
  22. }
  23.  
  24. void proc(vector<int> &pref, vector<int> &suf, function<int(int, int)> f, int def){
  25.     fil(pref, f, def);
  26.     reverse(suf.begin(), suf.end());
  27.     fil(suf, f, def);
  28.     reverse(suf.begin(), suf.end());
  29. }
  30.  
  31. void dfs_prep(int v, int par){
  32.     int cnt=0;
  33.     vector<int> ch, pref, suf;
  34.     dp_dn[v][0] = 1;
  35.     for(auto u : g[v]){
  36.         if(u == par)
  37.             continue;
  38.         cnt ++;
  39.         dfs_prep(u, v);
  40.         dp_dn[v][0] *= dp_dn[u][1];
  41.         ch.push_back(u);
  42.         pref.push_back(dp_dn[u][1]);
  43.         suf.push_back(dp_dn[u][1]);
  44.     }
  45.     dp_dn[v][1] = dp_dn[v][0];
  46.     proc(pref, suf, [&](int a, int b){return a*b;}, 1);
  47.     for(int i=0 ; i<ch.size() ; i++){
  48.         int cur = (i ? pref[i-1] : 1);
  49.         cur *= (i+1 < ch.size() ? suf[i+1] : 1);
  50.         cur *= dp_dn[ ch[i] ][0];
  51.         dp_dn[v][1] ^= cur;
  52.     }
  53. }
  54.  
  55. int ans;
  56.  
  57. void dfs(int v=0, int par=-1, int up_used=0, int up_unused=1){
  58.     if(par >= 0){
  59.         int w = mp[ii(v, par)];
  60.         ans ^= up_used * dp_dn[v][0] * w;
  61.     }
  62.     vector<int> used, unused, ch, pref, suf, ppref, ssuf;
  63.     for(auto u : g[v]){
  64.         if(u == par)
  65.             continue;
  66.         ch.push_back(u);
  67.         pref.push_back(dp_dn[u][1]);
  68.         suf.push_back(dp_dn[u][1]);
  69.         used.push_back(0);
  70.         unused.push_back(0);
  71.     }
  72.     proc(pref, suf, [&](int a, int b){return a*b;}, 1);
  73.     for(int i=0 ; i<ch.size() ; i++){
  74.         int cur = (i ? pref[i-1] : 1);
  75.         cur *= (i+1 < ch.size() ? suf[i+1] : 1);
  76.         used[i] ^= cur * up_unused;
  77.         unused[i] ^= cur * (up_used ^ up_unused);
  78.         ppref.push_back(dp_dn[ ch[i] ][0] * (i ? pref[i-1] : 1));
  79.         ssuf.push_back(dp_dn[ ch[i] ][0] * (i+1 < ch.size() ? suf[i+1] : 1));
  80.     }
  81.     if(!ch.empty()){ // left
  82.         int pp = ppref[0];
  83.         for(int i=1 ; i<ch.size() ; i++){
  84.             int cur = pp * (i+1 < ch.size() ? suf[i+1] : 1);
  85.             unused[i] ^= cur * up_unused;
  86.             if(!dp_dn[ ch[i] ][1])
  87.                 pp = 0;
  88.             pp ^= ppref[i];
  89.         }
  90.     }
  91.     if(!ch.empty()){ // right
  92.         int ss = ssuf[ch.size()-1];
  93.         dfs(ch.back(), v, used.back(), unused.back());
  94.         for(int i=(int)ch.size()-2 ; i>=0 ; i--){
  95.             int cur = ss * (i ? pref[i-1] : 1);
  96.             unused[i] ^= cur * up_unused;
  97.             int u = ch[i];
  98.             if(!dp_dn[u][1])
  99.                 ss = 0;
  100.             ss ^= ssuf[i];
  101.             dfs(u, v, used[i], unused[i]);
  102.         }
  103.     }
  104. }
  105.  
  106. signed main(){
  107.         ios_base::sync_with_stdio(false);cin.tie(NULL);
  108.     cin >> n;
  109.     for(int i=0 ; i<n-1 ; i++){
  110.         int v, u, w;cin >> v >> u >> w;v --;u --;
  111.         g[v].push_back(u);
  112.         g[u].push_back(v);
  113.         mp[ii(v, u)] = w;
  114.         mp[ii(u, v)] = w;
  115.     }
  116.     dfs_prep(0, -1);
  117.     dfs();
  118.     cout << ans << "\n";
  119. }
  120.