| 比赛 |
THUPC 2025 pre |
评测结果 |
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR |
| 题目名称 |
骑行计划 |
最终得分 |
0 |
| 用户昵称 |
yyswys |
运行时间 |
0.916 s |
| 代码语言 |
C++ |
内存使用 |
31.19 MiB |
| 提交时间 |
2026-01-29 19:04:18 |
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=6e5+5,inf=1e15;
struct node{
int v,w;
};
int n,dis[N],m;
int d[N],s[N],df[N],st[N][21],lg[N],t,si[N];
vector<node>e[N];
void dfs(int u,int p,int h,int mw){
df[u]=++t;s[t]=u;d[t]=h,dis[u]=mw;
for(auto i:e[u])if(i.v!=p){dfs(i.v,u,h+1,min(mw,i.w));s[++t]=u;d[t]=h;}
}
void init(){
for(int i=2;i<=t;i++)lg[i]=lg[i>>1]+1;
for(int i=1;i<=t;i++)st[i][0]=i;
for(int j=1;j<=20;j++)
for(int i=1;i+(1<<j)-1<=t;i++){
int a=st[i][j-1],b=st[i+(1<<(j-1))][j-1];
st[i][j]=d[a]<d[b]?a:b;
}
}
int lca(int u,int v){
int l=df[u],r=df[v];if(l>r)swap(l,r);
int k=lg[r-l+1],a=st[l][k],b=st[r-(1<<k)+1][k];
return d[a]<d[b]?s[a]:s[b];
}
vector<int>ve[N];
void build(vector<int>&a){
a.push_back(1);
sort(a.begin(),a.end(),[](int a,int b){
return df[a]<df[b];
});
int sz=a.size();
for(int i(0);i<sz-1;++i){
a.push_back(lca(a[i],a[i+1]));
}
sort(a.begin(),a.end(),[](int a,int b){
return df[a]<df[b];
});
a.erase(unique(a.begin(),a.end()),a.end());
for(int i(0);i<(int)a.size()-1;++i){
int lc=lca(a[i],a[i+1]);
ve[lc].push_back(a[i+1]);
}
}
int sl(int u){
if(si[u]){ve[u].clear();return dis[u];}
int sum=0;
for(int v:ve[u]) sum+=sl(v);
ve[u].clear();
if(sum==0) return inf;
return min(dis[u],sum);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i(1);i<n;++i){
int u,v,w;
cin>>u>>v>>w;
e[u].push_back({v,w});
e[v].push_back({u,w});
}
dfs(1,0,1,inf);
init();
cin>>m;
while(m--){
int k;
cin>>k;
vector<int>q(k);
for(int i(0);i<k;++i){
cin>>q[i];
si[q[i]]=1;
}
vector<int>tq=q;
build(tq);
int ans=sl(1);
cout<<(ans>=inf?0:ans)<<"\n";
for(int x:q) si[x]=0;
}
return 0;
}