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 "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. struct HashTable {
  71.     struct Node{int k,v,nx;};
  72.     static vector<Node> pool;
  73.     static int ptr;
  74.     vector<int> head;
  75.     int B;
  76.     HashTable():B(0){}
  77.     inline uint64_t hsh(uint64_t x) const {
  78.         x+=0x9e3779b97f4a7c15ULL;
  79.         x=(x^(x>>30))*0xbf58476d1ce4e5b9ULL;
  80.         x=(x^(x>>27))*0x94d049bb133111ebULL;
  81.         x^=(x>>31);
  82.         return x;
  83.     }
  84.     void max_load_factor(float) {}
  85.     void reserve(size_t nb){ resize((int)nb*2+3); }
  86.     void resize(int nb){
  87.         if(nb<1) nb=1;
  88.         int b=1; while(b<nb) b<<=1;
  89.         B=b; head.assign(B,-1);
  90.     }
  91.     struct iterator{
  92.         int id;
  93.         mutable pii tmp;
  94.         iterator(int _id=-1):id(_id){}
  95.         pii* operator->() const {
  96.             if(id!=-1){ tmp.fi=HashTable::pool[id].k; tmp.se=HashTable::pool[id].v; }
  97.             return &tmp;
  98.         }
  99.         bool operator==(const iterator& o) const { return id==o.id; }
  100.         bool operator!=(const iterator& o) const { return id!=o.id; }
  101.     };
  102.     iterator end() const { return iterator(-1); }
  103.     iterator find(int k){
  104.         if(!B) return end();
  105.         int b=(int)(hsh((uint64_t)(unsigned)k)&(uint64_t)(B-1));
  106.         for(int i=head[b]; i!=-1; i=pool[i].nx) if(pool[i].k==k) return iterator(i);
  107.         return end();
  108.     }
  109.     int& operator[](int k){
  110.         if(!B) resize(4);
  111.         int b=(int)(hsh((uint64_t)(unsigned)k)&(uint64_t)(B-1));
  112.         for(int i=head[b]; i!=-1; i=pool[i].nx) if(pool[i].k==k) return pool[i].v;
  113.         pool.push_back({k,0,head[b]}); head[b]=ptr++; return pool.back().v;
  114.     }
  115.     void erase(int k){
  116.         if(!B) return;
  117.         int b=(int)(hsh((uint64_t)(unsigned)k)&(uint64_t)(B-1));
  118.         int i=head[b], p=-1;
  119.         while(i!=-1){
  120.             if(pool[i].k==k){
  121.                 if(p==-1) head[b]=pool[i].nx; else pool[p].nx=pool[i].nx;
  122.                 return;
  123.             }
  124.             p=i; i=pool[i].nx;
  125.         }
  126.     }
  127. };
  128. vector<HashTable::Node> HashTable::pool;
  129. int HashTable::ptr=0;
  130.  
  131. int n, q, ans=0;
  132. vpii g[maxn];
  133. int par[maxn], up[maxn], h[maxn];
  134. struct edge{int u, v, c;} e[maxn];
  135. HashTable mp[maxn];
  136. bool vs[maxn];
  137.  
  138. void dfs(int u)
  139. {
  140.     for(auto v:g[u]) if(v.fi!=par[u])
  141.     {
  142.         par[v.fi]=u; up[v.fi]=v.se; h[v.fi]=h[u]+1;
  143.         dfs(v.fi);
  144.     }
  145. }
  146.  
  147. void pre(int i)
  148. {
  149.     vs[i]=1;
  150.     int u=e[i].u, v=e[i].v, c=e[i].c;
  151.     for(auto id:g[u]) if(!vs[id.se])
  152.     {
  153.         if(e[id.se].c==c) pre(id.se);
  154.     }
  155.     for(auto id:g[v]) if(!vs[id.se])
  156.     {
  157.         if(e[id.se].c==c) pre(id.se);
  158.     }
  159. }
  160.  
  161. signed main()
  162. {
  163.     rf();
  164.     int sub; cin>>sub;
  165.     cin>>n;
  166.     ff(i, 1, n-1)
  167.     {
  168.         int u ,v, c; cin>>u>>v>>c;
  169.         e[i]={u, v, c};
  170.         g[u].pb(v, i); g[v].pb(u, i);
  171.     }
  172.     dfs(1);
  173.     ff(i, 1, n-1)
  174.     {
  175.         int &u=e[i].u, &v=e[i].v;
  176.         if(h[u]>h[v]) swap(u, v);
  177.     }
  178.     ff(i, 1, n-1) if(!vs[i]) ++ans, pre(i);
  179.     ff(i, 1, n)
  180.     {
  181.         mp[i].reserve(g[i].size());
  182.         for(auto x:g[i]) if(x.fi!=par[i]) ++mp[i][e[x.se].c];
  183.     }
  184.     cout<<ans<<ss;
  185.     cin>>q;
  186.     while(q--)
  187.     {
  188.         int i, nc; cin>>i>>nc;
  189.         if(nc!=e[i].c)
  190.         {
  191.             int &u=e[i].u, &v=e[i].v, &c=e[i].c;
  192.             int parid=up[u];
  193.             bool ok1=(mp[v].find(c)!=mp[v].end());
  194.             auto it=mp[u].find(c);
  195.             bool ok2=((it!=mp[u].end() && (it->se)>=2) || e[parid].c==c);
  196.             if(ok1) ++ans;
  197.             if(ok2) ++ans;
  198.             if(--mp[u][c]==0) mp[u].erase(c);
  199.             c=nc;
  200.             ++mp[u][c];
  201.  
  202.             ok1=(mp[v].find(c)!=mp[v].end());
  203.             it=mp[u].find(c);
  204.             ok2=((it!=mp[u].end() && (it->se)>=2) || e[parid].c==c);
  205.             if(ok1) --ans;
  206.             if(ok2) --ans;
  207.         }
  208.         cout<<ans<<ss;
  209.     }
  210.     re;
  211. }
  212.  
Success #stdin #stdout 0.01s 20872KB
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/FrXfm0
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!