fork download
copy 
  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 "tree-edge-color-queries"
  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 push_back
  12. #define pb emplace_back
  13. #define fi first
  14. #define se second
  15. #define sz(s) (int)s.size()
  16. #define all(s) (s).begin(), (s).end()
  17. #define ms(a,x) memset(a, x, sizeof (a))
  18. #define cn continue
  19. #define re exit(0)
  20.  
  21. typedef long long ll;
  22. typedef unsigned long long ull;
  23. typedef long double ld;
  24. typedef vector<int> vi;
  25. typedef vector<ll> vll;
  26. typedef pair<int, int> pii;
  27. typedef pair<ll, ll> pll;
  28. typedef vector<pii> vpii;
  29. typedef vector<pll> vpll;
  30.  
  31. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  32. ll ran(ll l, ll r)
  33. {
  34.     return uniform_int_distribution<ll> (l, r)(rng);
  35. }
  36.  
  37. inline void rf()
  38. {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(nullptr); cout.tie(nullptr);
  41.     if(fopen(file".inp","r"))
  42.     {
  43.         freopen(file".inp","r",stdin);
  44.         freopen(file".out","w",stdout);
  45.     }
  46. }
  47.  
  48. const int mod=998244353;
  49. const int maxn=3e5+15;
  50. const ll inf=5e16;
  51.  
  52. template<typename T> inline void add(T &x, const T &y)
  53. {
  54.     x+=y;
  55.     if(x>=mod) x-=mod;
  56.     if(x<0) x+=mod;
  57. }
  58.  
  59. template<typename T> inline bool maxi(T &a, T b)
  60. {
  61.     if(a>=b) return 0;
  62.     a=b; return 1;
  63. }
  64.  
  65. template<typename T> inline bool mini(T &a, T b)
  66. {
  67.     if(a<=b) return 0;
  68.     a=b; return 1;
  69. }
  70.  
  71. int n, q;
  72. vpii g[maxn]; vi kq;
  73. int par[maxn], up[maxn], h[maxn];
  74. struct edge{int u, v, c;} e[maxn], ne[maxn];
  75. struct myhash
  76. {
  77.     static uint64_t splitmix64(uint64_t x)
  78.     {
  79.         x+=0x9e3779b97f4a7c15ULL;
  80.         x=(x^(x>>30))*0xbf58476d1ce4e5b9ULL;
  81.         x=(x^(x>>27))*0x94d049bb133111ebULL;
  82.         return x^(x>>31);
  83.     }
  84.     size_t operator()(uint64_t x) const
  85.     {
  86.         static const uint64_t FIXED=chrono::steady_clock::now().time_since_epoch().count();
  87.         return splitmix64(x+FIXED);
  88.     }
  89. };
  90. unordered_map<ll, int, myhash> mp;
  91.  
  92. void dfs(int u)
  93. {
  94.     for(auto v:g[u]) if(v.fi!=par[u])
  95.     {
  96.         par[v.fi]=u; up[v.fi]=v.se; h[v.fi]=h[u]+1;
  97.         dfs(v.fi);
  98.     }
  99. }
  100.  
  101. inline ll get(int u, int c)
  102. {
  103.     return 1ll*u*(n+1)+c;
  104. }
  105.  
  106. signed main()
  107. {
  108.     rf();
  109.     int sub; cin>>sub;
  110.     cin>>n;
  111.     mp.reserve(maxn*2); mp.max_load_factor(0.7f);
  112.     ff(i, 1, n-1)
  113.     {
  114.         int u ,v, c; cin>>u>>v>>c;
  115.         e[i]={u, v, c};
  116.         g[u].pb(v, i); g[v].pb(u, i);
  117.     }
  118.     dfs(1);
  119.     ff(i, 1, n-1)
  120.     {
  121.         int &u=e[i].u, &v=e[i].v;
  122.         if(h[u]>h[v]) swap(u, v);
  123.         ne[i]=e[i]; ne[i].c=n+1;
  124.     }
  125.     ff(i, 1, n) for(auto x:g[i]) if(x.fi!=par[i]) ++mp[get(i, n+1)];
  126.  
  127.     int ans=1;
  128.     ff(i ,1, n-1)
  129.     {
  130.         int &u=ne[i].u, &v=ne[i].v, &c=ne[i].c;
  131.         int nc=e[i].c;
  132.         int parid=up[u];
  133.         bool ok1=(mp.find(get(v, c))!=mp.end());
  134.         bool ok2=((mp.find(get(u, c))!=mp.end() && mp[get(u, c)]>=2) || ne[parid].c==c);
  135.         if(ok1) ++ans;
  136.         if(ok2) ++ans;
  137.  
  138.         if(--mp[get(u, c)]==0) mp.erase(get(u, c));
  139.         c=nc;
  140.         ++mp[get(u, c)];
  141.  
  142.         ok1=(mp.find(get(v, c))!=mp.end());
  143.         ok2=((mp.find(get(u, c))!=mp.end() && mp[get(u, c)]>=2) || ne[parid].c==c);
  144.         if(ok1) --ans;
  145.         if(ok2) --ans;
  146.     }
  147.     kq.pb(ans);
  148.  
  149.     cin>>q;
  150.     while(q--)
  151.     {
  152.         int i, nc; cin>>i>>nc;
  153.         if(nc!=e[i].c)
  154.         {
  155.             int &u=e[i].u, &v=e[i].v, &c=e[i].c;
  156.             int parid=up[u];
  157.             bool ok1=(mp.find(get(v, c))!=mp.end());
  158.             bool ok2=((mp.find(get(u, c))!=mp.end() && mp[get(u, c)]>=2) || e[parid].c==c);
  159.             if(ok1) ++ans;
  160.             if(ok2) ++ans;
  161.  
  162.             if(--mp[get(u, c)]==0) mp.erase(get(u, c));
  163.             c=nc;
  164.             ++mp[get(u, c)];
  165.  
  166.             ok1=(mp.find(get(v, c))!=mp.end());
  167.             ok2=((mp.find(get(u, c))!=mp.end() && mp[get(u, c)]>=2) || e[parid].c==c);
  168.             if(ok1) --ans;
  169.             if(ok2) --ans;
  170.         }
  171.         kq.pb(ans);
  172.     }
  173.     for(auto x:kq) cout<<x<<ss;
  174.     re;
  175. }
  176.  
Success #stdin #stdout 0.01s 19056KB
comments (?)
stdin
copy 
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
copy 
4 6 5
https://ideone.com/YVRz65
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!