比赛 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;
}