結果
問題 | No.901 K-ary εxtrεεmε |
ユーザー |
👑 ![]() |
提出日時 | 2020-09-27 19:55:49 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 333 ms / 3,000 ms |
コード長 | 1,392 bytes |
コンパイル時間 | 1,773 ms |
コンパイル使用メモリ | 178,372 KB |
実行使用メモリ | 24,356 KB |
最終ジャッジ日時 | 2024-06-30 12:53:59 |
合計ジャッジ時間 | 9,237 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 29 |
ソースコード
#include<bits/stdc++.h> using namespace std; using LL=long long; using ULL=unsigned long long; #define rep(i,n) for(int i=0; i<(n); i++) const int xN=100000; struct Edge{ int to; LL dist; }; int N; vector<Edge> E[xN]; int P[xN]; LL D[xN]; int dfsI[xN]; int lcaP[20][xN]; int lcaD[xN]; int dfs(int p=0,int i=0){ dfsI[p] = i++; for(Edge& e:E[p]){ if(P[p]==e.to) continue; D[e.to] = D[p] + e.dist; lcaD[e.to] = lcaD[p] + 1; P[e.to] = p; i = dfs(e.to,i); } return i; } void init(){ rep(i,N) P[i]=-1; rep(i,N) D[i]=0; dfs(0); rep(i,N) lcaP[0][i] = P[i]; lcaP[0][0] = 0; rep(d,19) rep(i, N) lcaP[d + 1][i] = lcaP[d][lcaP[d][i]]; } int LCA(int u,int v){ if(lcaD[u]>lcaD[v]) swap(u,v); for(int i=19; i>=0; i--) if(lcaD[u] + (1<<i) <= lcaD[v]) v=lcaP[i][v]; if(u==v) return u; for(int i=19; i>=0; i--) if(lcaP[i][u] != lcaP[i][v]){ u=lcaP[i][u]; v=lcaP[i][v]; } return lcaP[0][u]; } LL distance(int u,int v){ int g=LCA(u,v); return D[u]+D[v]-2*D[g]; } int main(){ cin>>N; rep(i,N-1){ int u,v,c; cin>>u>>v>>c; E[u].push_back({v,c}); E[v].push_back({u,c}); } init(); int Q; cin>>Q; while(Q--){ int K; cin>>K; vector<pair<int,int>> X(K); rep(i,K){ int x; cin>>x; X[i] = {dfsI[x],x}; } sort(X.begin(),X.end()); X.push_back(X.front()); LL ans=0; rep(i,K) ans += distance(X[i].second,X[i+1].second); cout<<(ans/2)<<endl; } return 0; }