蒟蒻刚学虚树,WA求助
查看原帖
蒟蒻刚学虚树,WA求助
914961
liaoz123楼主2024/1/23 18:56

全WA,样例可过,对着第一篇题解抄的,检查了一小时了不知道哪里有问题。

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll; 
const int N=1e6+5;
const ll inf=2e16;
struct node{
	int nxt,to;ll dis;
}e[N<<1],ee[N<<1];
int num,numm,head[N],n,qq,dfn[N],tim,fa[N][21];
int dep[N],l[N],p[N],top,q[N],h[N];
bool vis[N];
ll f[N];
void add(int x,int y,ll z){
	e[++num]=node{head[x],y,z};head[x]=num;
}
void ad(int x,int y){
	ee[++numm]=node{h[x],y};h[x]=numm;
}
void dfs(int u){
	dfn[u]=++tim;
	for(int i=1;i<=20;i++)
	fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(dfn[v])continue;
		f[v]=min(f[u],e[i].dis);
		fa[v][0]=u;dep[v]=dep[u]+1;
		dfs(v);
	}
}
ll dfs1(int u){
	ll ss=0,tmp;
	for(int i=h[u];i;i=ee[i].nxt){
		int v=ee[i].to;
		ss+=dfs1(v);
	}if(vis[u])tmp=f[u];
	else tmp=min(ss,f[u]);
	h[u]=0;vis[u]=false;
	return tmp;
}
int LCA(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	while(dep[x]!=dep[y])x=fa[x][l[dep[x]-dep[y]]];
	if(x==y)return x;
	for(int i=20;i;i--)
	if(fa[x][i]!=fa[y][i])
	x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
bool cmp(int x,int y){return dfn[x]<dfn[y];}
signed main(){
	f[1]=inf;
	cin>>n;int k;
	for(int i=2;i<N;i++)l[i]=l[i>>1]+1;
	for(int i=1;i<n;i++){
		int x,y,z;scanf("%lld%lld%lld",&x,&y,&z);
		add(x,y,z);add(y,x,z);
	}dfs(1);cin>>qq;
	while(qq--){
		cin>>k;numm=0;
		for(int i=1;i<=k;i++){
			scanf("%lld",&p[i]);
			vis[p[i]]=true;
		}
		sort(p+1,p+k+1,cmp);
		q[top=1]=p[1];
		for(int i=2;i<=k;i++){
			int now=p[i];
			int lca=LCA(now,q[top]);
			while(true){
				if(dep[lca]>=dep[q[top-1]]){
					if(lca!=q[top]){
						ad(lca,q[top]);
						if(lca!=q[top-1])
						q[top]=lca;
						else top--;
					}
					break;
				}
				else ad(q[top-1],q[top]),top--;
			}
			q[++top]=now;
		}
		while(--top)ad(q[top],q[top+1]);
		cout<<dfs1(q[1])<<endl;
	}
	return 0;
}
2024/1/23 18:56
加载中...