結果
問題 | No.2892 Lime and Karin |
ユーザー |
|
提出日時 | 2024-09-13 22:00:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 261 ms / 8,000 ms |
コード長 | 1,377 bytes |
コンパイル時間 | 1,045 ms |
コンパイル使用メモリ | 77,712 KB |
実行使用メモリ | 18,632 KB |
最終ジャッジ日時 | 2024-09-13 22:01:14 |
合計ジャッジ時間 | 8,825 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 52 |
ソースコード
#include<iostream> #include<algorithm> #include<vector> #include<cassert> using namespace std; int N; string S; vector<int>G[1<<17]; int sz[1<<17]; bool vis[1<<17]; void dfs_sz(int u,int p) { sz[u]=1; for(int v:G[u])if(!vis[v]&&v!=p) { dfs_sz(v,u); sz[u]+=sz[v]; } } vector<int>V; void dfs1(int u,int p,int cur) { cur+=S[u]=='1'?1:-1; V.push_back(cur); for(int v:G[u])if(!vis[v]&&v!=p)dfs1(v,u,cur); } long ans; long solve(vector<int>&V,int add) { sort(V.begin(),V.end()); long ret=0; int j=V.size(); for(int i=0;i<V.size();i++) { while(j>0&&V[i]+V[j-1]+add>0)j--; ret+=V.size()-max(i,j); } return ret; } void dfs(int u) { dfs_sz(u,-1); int root=u; { int p=-1; while(true) { bool fn=false; for(int v:G[root])if(!vis[v]&&v!=p&&sz[v]>sz[u]/2) { p=root; root=v; fn=true; break; } if(!fn)break; } } int add=S[root]=='1'?1:-1; vector<int>All; All.reserve(sz[u]); All.push_back(0); V.reserve(sz[u]/2); for(int v:G[root])if(!vis[v]) { V.clear(); dfs1(v,root,0); ans-=solve(V,add); for(int w:V)All.push_back(w); } ans+=solve(All,add); vis[root]=true; for(int v:G[root])if(!vis[v])dfs(v); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>N; for(int i=1;i<N;i++) { int u,v;cin>>u>>v; u--,v--; G[u].push_back(v); G[v].push_back(u); } cin>>S; dfs(0); cout<<ans<<endl; }