結果
問題 | No.1718 Random Squirrel |
ユーザー |
![]() |
提出日時 | 2021-12-17 23:54:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 93 ms / 2,000 ms |
コード長 | 2,290 bytes |
コンパイル時間 | 1,058 ms |
コンパイル使用メモリ | 83,220 KB |
最終ジャッジ日時 | 2025-01-27 02:45:24 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>using namespace std;typedef long long ll;vector<int> G[200010];ll sum[200010],mx1[200010],mx2[200010],a[200010];void dfs1(int s,int p){sum[s] += a[s];for(int v:G[s]){if(v==p) continue;dfs1(v,s);sum[s] += sum[v];}}void dfs2(int s,int p){ll ret = -100000000;for(int v:G[s]){if(v==p) continue;dfs2(v,s);ret = max(ret,mx1[v]);}mx1[s] = ret + 1;if(a[s]) mx1[s] = max(mx1[s],0LL);}int init = 0;void dfs3(int s,int p){init++;for(int v:G[s]){if(v==p || sum[v]==0) continue;dfs3(v,s);}}ll ans[200010];void reroot1(int s,int p,ll now,ll cnt){ans[s] = now;for(int v:G[s]){if(v==p) continue;if(sum[v]==0) reroot1(v,s,now + 2,cnt);else if(sum[v]==cnt) reroot1(v,s,now - 2,cnt);else reroot1(v,s,now,cnt);}}void reroot2(int s,int p,ll now){mx2[s] = now;if(a[s]) mx2[s] = max(mx2[s],0LL);vector<pair<ll,int>> vec;for(int v:G[s]){if(v==p) continue;vec.push_back({mx1[v],v});}sort(vec.begin(),vec.end());if(vec.size()==0) return;if(vec.size()==1){for(int v:G[s]){if(v==p) continue;reroot2(v,s,mx2[s] + 1);}}else{for(int v:G[s]){if(v==p) continue;if(v==vec.back().second) reroot2(v,s,max(mx2[s] + 1,vec[vec.size() - 2].first + 2));else reroot2(v,s,max(mx2[s] + 1,vec.back().first + 2));}}}int main(){ios_base::sync_with_stdio(false);cin.tie(NULL);int i,n,k; cin >> n >> k;for(i=0;i<n - 1;i++){int u,v; cin >> u >> v; u--; v--;G[u].push_back(v); G[v].push_back(u);}for(i=0;i<k;i++){int x; cin >> x; x--; a[x]++;}dfs1(0,-1); dfs2(0,-1); dfs3(0,-1);init--; init *= 2;reroot1(0,-1,init,k);reroot2(0,-1,-1000000000);/*for(i=0;i<n;i++) cout << ans[i] << " ";cout << endl;for(i=0;i<n;i++) cout << mx1[i] << " ";cout << endl;for(i=0;i<n;i++) cout << mx2[i] << " ";cout << endl;*/for(i=0;i<n;i++) ans[i] -= max(mx1[i],mx2[i]);for(i=0;i<n;i++) cout << ans[i] << "\n";}