結果
問題 | No.1002 Twotone |
ユーザー |
![]() |
提出日時 | 2020-02-28 22:44:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4,526 ms / 5,000 ms |
コード長 | 4,066 bytes |
コンパイル時間 | 4,078 ms |
コンパイル使用メモリ | 241,992 KB |
最終ジャッジ日時 | 2025-01-09 03:04:05 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 |
ソースコード
#include<bits/stdc++.h> using namespace std; using Int = long long; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} struct Centroid{ vector<int> sz,dead; vector< vector<int> > G; Centroid(){} Centroid(int n):sz(n,1),dead(n,0),G(n){} void add_edge(int u,int v){ G[u].emplace_back(v); G[v].emplace_back(u); } int dfs(int v,int p){ sz[v]=1; for(int u:G[v]) if(u!=p&&!dead[u]) sz[v]+=dfs(u,v); return sz[v]; } void find(int v,int p,int tmp,vector<int> &cs) { int ok=1; for (int u:G[v]){ if(u==p||dead[u]) continue; find(u,v,tmp,cs); ok&=(sz[u]<=tmp/2); } ok&=(tmp-sz[v]<=tmp/2); if(ok) cs.push_back(v); } vector<int> build(int r) { int tmp=dfs(r,-1); vector<int> cs; find(r,-1,tmp,cs); return cs; } void disable(int v){ dead[v]=1; } void enable(int v){ dead[v]=0; } int alive(int v){ return !dead[v]; } }; template<typename F> struct FixPoint : F{ FixPoint(F&& f):F(forward<F>(f)){} template<typename... Args> decltype(auto) operator()(Args&&... args) const{ return F::operator()(*this,forward<Args>(args)...); } }; template<typename F> inline decltype(auto) MFP(F&& f){ return FixPoint<F>{forward<F>(f)}; } struct FastIO{ FastIO(){ cin.tie(0); ios::sync_with_stdio(0); } }fastio_beet; #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template<typename T,typename U, typename H=hash<T> > using gmap = cc_hash_table<T, U, H>; //INSERT ABOVE HERE signed main(){ using ll = long long; int n,k; cin>>n>>k; k++;k++; vector< gmap<int, int> > col(n); Centroid G(n); for(int i=1;i<n;i++){ int x,y,z; cin>>x>>y>>z; x--;y--;z--; G.add_edge(x,y); col[x][y]=z; col[y][x]=z; } queue<int> que; que.emplace(G.build(0)[0]); ll ans=0,all=0; vector<ll> cnt(k,0),uku(k,0); auto P=[&](int x,int y){return (ll)x*k+y;}; auto calc= [&](ll p,int q)->ll{ int x=p/k,y=p%k; if(x==q||y==q) return p; if(y==k-1) return P(min(x,q),max(x,q)); return P(k-1,k-1); }; while(!que.empty()){ int r=que.front();que.pop(); gmap<ll, int> num; for(int t:G.G[r]){ if(!G.alive(t)) continue; // count MFP([&](auto dfs,int v,int p,ll st)->void{ if(st==P(k-1,k-1)) return; for(int u:G.G[v]){ if(u==p) continue; if(!G.alive(u)) continue; dfs(u,v,calc(st,col[u][v])); } if(st%k==k-1){ ans+=all-cnt[st/k]; ans+=uku[st/k]; }else{ ans+=1; ans+=cnt[st/k]; ans+=cnt[st%k]; ans+=num[st]; } })(t,r,P(col[r][t],k-1)); // paint MFP([&](auto dfs,int v,int p,ll st)->void{ if(st==P(k-1,k-1)) return; for(int u:G.G[v]){ if(u==p) continue; if(!G.alive(u)) continue; dfs(u,v,calc(st,col[u][v])); } if(st%k==k-1){ cnt[st/k]++; all++; }else{ num[st]++; uku[st/k]++; uku[st%k]++; } })(t,r,P(col[r][t],k-1)); } for(int t:G.G[r]){ if(!G.alive(t)) continue; // clear MFP([&](auto dfs,int v,int p,ll st)->void{ if(st==P(k-1,k-1)) return; for(int u:G.G[v]){ if(u==p) continue; if(!G.alive(u)) continue; dfs(u,v,calc(st,col[u][v])); } if(st%k==k-1){ cnt[st/k]--; all--; }else{ num[st]--; uku[st/k]--; uku[st%k]--; } })(t,r,P(col[r][t],k-1)); } G.disable(r); for(int u:G.G[r]) if(G.alive(u)) que.emplace(G.build(u)[0]); } cout<<ans<<endl; return 0; }