WA on#10求助
查看原帖
WA on#10求助
925506
ACRUSHj楼主2023/7/3 20:51

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e5+5e4+10;
struct edge{int ed,w;};
int n,m,f[N][21],o[N][20],dep[N],dfn[N],q1[N],q2[N];
bool key[N];LL dp[N];
vector<edge>e[N];vector<edge>E[N];
bool cmp(int x,int y){
	return dfn[x]<dfn[y];
}
void dfs(int u){
	dfn[u]=++dfn[0];dep[u]=dep[f[u][0]]+1;
	for(int i=1;(1<<i)<=dep[u];i++)f[u][i]=f[f[u][i-1]][i-1];
	for(int i=1;(1<<i)<=dep[u];i++)o[u][i]=min(o[u][i-1],o[f[u][i-1]][i-1]);
	for(auto x:e[u])if(x.ed!=f[u][0]){
		int v=x.ed;
		f[v][0]=u;o[v][0]=x.w; 
		dfs(v);
	}
	return;
}
int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	for(int i=20;i>=0;i--)
		if(dep[f[x][i]]>=dep[y])x=f[x][i];
	if(x==y)return x;
	for(int i=20;i>=0;i--)
		if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
	return f[x][0];
}
int Dmin(int x,int y){
	swap(x,y);
	int ret=1e9;
	for(int i=20;i>=0;i--)
		if(dep[f[x][i]]>=dep[y])ret=min(ret,o[x][i]),x=f[x][i];
	return ret;
}
void DP(int u,int fa){
	for(auto x:E[u]){
		int v=x.ed;
		if(v!=fa){
			DP(v,u);
			if(key[v])dp[u]+=x.w;
			else dp[u]+=min(1ll*x.w,dp[v]);
		}
	}
	return;
}
LL solve(){
	q2[0]=0;
	sort(q1+1,q1+q1[0]+1,cmp);
	for(int i=1;i<q1[0];i++)
		q2[++q2[0]]=q1[i],q2[++q2[0]]=lca(q1[i],q1[i+1]);
	q2[++q2[0]]=q1[q1[0]];
	sort(q2+1,q2+q2[0]+1);
	q2[0]=unique(q2+1,q2+q2[0]+1)-q2-1;
	sort(q2+1,q2+q2[0]+1,cmp);
	for(int i=1;i<=q2[0];i++)E[q2[i]].clear();
	for(int i=1;i<q2[0];i++){
		dp[q2[i]]=0;
		int LCA=lca(q2[i],q2[i+1]),W=Dmin(LCA,q2[i+1]);
		E[LCA].push_back({q2[i+1],W});
		E[q2[i+1]].push_back({LCA,W});
	}dp[q2[q2[0]]]=0;
//	for(int i=1;i<=q2[0];i++){
//		printf("%d:",q2[i]);
//		for(auto x:E[q2[i]])printf("%d %d|",x.ed,x.w);
//		puts("");
//	}
	DP(1,0);
	return dp[1];
}
signed main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		e[x].push_back({y,z});e[y].push_back({x,z});
	}
	memset(o,0x3f,sizeof(o));
	dfs(1);key[1]=1;
	scanf("%d",&m);
	for(int i=1,num;i<=m;i++){
		scanf("%d",&num);
		for(int j=1;j<=num;j++)scanf("%d",&q1[++q1[0]]),key[q1[q1[0]]]=1;
		q1[++q1[0]]=1; 
		printf("%lld\n",solve());
		for(int j=1;j<=q1[0];j++)key[q1[j]]=0;q1[0]=0;
	}
	system("pause");
	return 0;
} 
2023/7/3 20:51
加载中...