fork download 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "o"
  7. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  8. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  9. #define nl "\n"
  10. #define ss " "
  11. #define pb emplace_back
  12. #define fi first
  13. #define se second
  14. #define sz(s) (int)s.size()
  15. #define all(s) (s).begin(), (s).end()
  16. #define ms(a,x) memset(a, x, sizeof (a))
  17. #define cn continue
  18. #define re exit(0)
  19.  
  20. typedef long long ll;
  21. typedef unsigned long long ull;
  22. typedef long double ld;
  23. typedef vector<int> vi;
  24. typedef vector<ll> vll;
  25. typedef pair<int, int> pii;
  26. typedef pair<ll, ll> pll;
  27. typedef vector<pii> vpii;
  28. typedef vector<pll> vpll;
  29.  
  30. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  31. ll ran(ll l, ll r)
  32. {
  33.     return uniform_int_distribution<ll> (l, r)(rng);
  34. }
  35.  
  36. inline void rf()
  37. {
  38.     ios_base::sync_with_stdio(false);
  39.     cin.tie(nullptr); cout.tie(nullptr);
  40.     if(fopen(file".inp","r"))
  41.     {
  42.         freopen(file".inp","r",stdin);
  43.         freopen(file".out","w",stdout);
  44.     }
  45. }
  46.  
  47. const int mod=998244353;
  48. const int maxn=3e5+15;
  49. const ll inf=5e16;
  50.  
  51. template<typename T> inline void add(T &x, const T &y)
  52. {
  53.     x+=y;
  54.     if(x>=mod) x-=mod;
  55.     if(x<0) x+=mod;
  56. }
  57.  
  58. template<typename T> inline bool maxi(T &a, T b)
  59. {
  60.     if(a>=b) return 0;
  61.     a=b; return 1;
  62. }
  63.  
  64. template<typename T> inline bool mini(T &a, T b)
  65. {
  66.     if(a<=b) return 0;
  67.     a=b; return 1;
  68. }
  69.  
  70. int n, q, ans=0;
  71. vpii g[maxn]; vi kq;
  72. int par[maxn], up[maxn], h[maxn];
  73. struct edge{int u, v, c;} e[maxn];
  74.  
  75. struct chash {
  76.     static inline uint64_t splitmix64(uint64_t x) {
  77.         x += 0x9e3779b97f4a7c15ULL;
  78.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
  79.         x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
  80.         return x ^ (x >> 31);
  81.     }
  82.     size_t operator()(uint64_t x) const noexcept {
  83.         static const uint64_t FIXED_RANDOM =
  84.             chrono::steady_clock::now().time_since_epoch().count();
  85.         return splitmix64(x + FIXED_RANDOM);
  86.     }
  87. };
  88. static inline uint64_t KEY(int u, int c) {
  89.     return ( (uint64_t)u << 32 ) ^ (uint32_t)c;
  90. }
  91. unordered_map<uint64_t,int,chash> cnt;
  92.  
  93. void dfs(int s)
  94. {
  95.     vector<int> st; st.pb(s);
  96.     par[s]=0; up[s]=0; h[s]=0;
  97.     while(!st.empty())
  98.     {
  99.         int u=st.back(); st.pop_back();
  100.         for(auto v:g[u]) if(v.fi!=par[u])
  101.         {
  102.             par[v.fi]=u; up[v.fi]=v.se; h[v.fi]=h[u]+1;
  103.             st.pb(v.fi);
  104.         }
  105.     }
  106. }
  107.  
  108. signed main()
  109. {
  110.     rf();
  111.     int sub; cin>>sub;
  112.     cin>>n;
  113.     ff(i, 1, n-1)
  114.     {
  115.         int u ,v, c; cin>>u>>v>>c;
  116.         e[i]={u, v, c};
  117.         g[u].pb(v, i); g[v].pb(u, i);
  118.     }
  119.  
  120.     dfs(1);
  121.  
  122.     ff(i, 1, n-1)
  123.     {
  124.         int &u=e[i].u, &v=e[i].v;
  125.         if(h[u]>h[v]) swap(u, v);
  126.     }
  127.  
  128.     cnt.reserve((n-1)*2);
  129.     ff(i, 1, n-1) ++cnt[KEY(e[i].u, e[i].c)];
  130.  
  131.     {
  132.         long long A = n - 1;
  133.         for (auto &kv : cnt) A -= (kv.se - 1);
  134.         ff(v, 1, n)
  135.         {
  136.             int parid = up[v];
  137.             if(parid)
  138.             {
  139.                 int pc = e[parid].c;
  140.                 if (cnt.find(KEY(v, pc)) != cnt.end()) --A;
  141.             }
  142.         }
  143.         ans = (int)A;
  144.     }
  145.  
  146.     kq.pb(ans);
  147.  
  148.     cin>>q;
  149.     while(q--)
  150.     {
  151.         int i, nc; cin>>i>>nc;
  152.         if(nc!=e[i].c)
  153.         {
  154.             int &u=e[i].u, &v=e[i].v, &c=e[i].c;
  155.             int parid=up[u];
  156.  
  157.             if (cnt.find(KEY(v, c)) != cnt.end()) ++ans;
  158.  
  159.             {
  160.                 auto it = cnt.find(KEY(u, c));
  161.                 int cu = (it==cnt.end()?0:it->second); 
  162.                 if (cu>=2 || (parid && e[parid].c==c)) ++ans;
  163.             }
  164.             {
  165.                 auto it = cnt.find(KEY(u, c));
  166.                 if (it!=cnt.end())
  167.                 {
  168.                     if (--(it->second)==0) cnt.erase(it);
  169.                 }
  170.             }
  171.             c=nc;
  172.             ++cnt[KEY(u, nc)];
  173.             if (cnt.find(KEY(v, nc)) != cnt.end()) --ans;
  174.  
  175.             {
  176.                 auto it2 = cnt.find(KEY(u, nc));
  177.                 int cu2 = (it2==cnt.end()?0:it2->second);
  178.                 if (cu2>=2 || (parid && e[parid].c==nc)) --ans;
  179.             }
  180.         }
  181.         kq.pb(ans);
  182.     }
  183.  
  184.     for(auto x:kq) cout<<x<<ss;
  185.     re;
  186. }
  187.  
Success #stdin #stdout 0.01s 14360KB
comments (?)
stdin 
1
9
1 2 1
1 3 1
3 4 2
4 8 2
3 6 2
6 7 2
3 5 3
2 9 5
2
3 4
4 4
stdout 
4 6 5
https://ideone.com/hxMxY3
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!