萌新虚树求调,有注释,必关
查看原帖
萌新虚树求调,有注释,必关
978200
aqzjklo楼主2025/8/2 09:13

wa+tle0pts,样例通过

#include <bits/stdc++.h>
using namespace std;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
    return;
}

int n,m,s=1,k,dfn[250005],ans[250005];
bool dr[250005];
vector<int> q;
bool cmp(int x, int y)
{
	return dfn[x]<dfn[y];//按时间戳排序 
}

int head[250005],cnt,head1[250005],cnt1;
struct dck 
{
	int nxt,to,ed;
} a[500005],b[500005];
void add(int x,int y,int w)
{
	a[++cnt].nxt=head[x];
	head[x]=cnt;
	a[cnt].ed=w;
	a[cnt].to=y;
}
void add2(int x,int y,int w)//虚树加边 
{
	b[++cnt1].nxt=head1[x];
	head1[x]=cnt1;
	b[cnt1].ed=w;
	b[cnt1].to=y;
}

int f[250005][20],dep[250005],dp[250005][25];//f为祖先,dp为链上的最小值,dep为深度 
void dfs1(int now,int fa,int id)//预处理lca 
{
	dfn[now]=id;
	f[now][0]=fa;
	dep[now]=dep[fa]+1;
	
	for (int i=1;i<=19; i++) 
	{
		f[now][i]=f[f[now][i-1]][i-1];
	}
	
	for (int i=head[now]; i; i=a[i].nxt)
	{
		if (a[i].to==fa) continue;
		dp[a[i].to][0]=a[i].ed;
		dfs1(a[i].to,now,++id);
	}
}

void dfs2(int now,int fa)//求解答案 
{
	for (int i=head1[now]; i; i=b[i].nxt)
	{
		if (b[i].to==fa) continue;
		dfs2(b[i].to,now);
		if (dr[b[i].to]) ans[now]+=b[i].ed;
		else ans[now]+=min(ans[b[i].to],b[i].ed);
	}
}

int ww;
int lca(int x,int y)
{
	bool ok=0;
	ww=0x3f3f3f3f3f;
	if (dep[x]>dep[y])
	{
		swap(x,y);
		ok=1;
	}
	
	int tep=dep[y]-dep[x];
	for (int j=0; tep; j++,tep>>=1)
	{
		if (tep&1)
		{
			if (!ok)//只求时间戳更大的一边的贡献 
			{
				ww=min(ww,dp[y][j]);
			}
			y=f[y][j];
		}
	} 
	
	if (y==x) return x;
	if (ok) swap(x,y);
	
	for (int j=19; j>=0&&y!=x; j--)
	{
		if (f[x][j]!=f[y][j])
		{
			ww=min(ww,dp[y][j]);
			x=f[x][j];
			y=f[y][j];
		}
	}
	
	ww=min(dp[y][0],ww); 
	return f[x][0];
}

int main()
{
	memset(dp,0x3f,sizeof(dp));
	
	n=read();
	for (int i=1; i<n; i++)
	{
		int x,y,z;
		x=read(),y=read(),z=read();
		add(x,y,z);
		add(y,x,z);
	}
	
	dfs1(s,0,1);
	for (int i=1; i<=19; i++)
	{
		for (int j=1; j<=n; j++)
		{
			dp[j][i]=min(dp[f[j][i-1]][i-1],dp[j][i-1]);//预处理倍增最小值 
		}
	}
	
	m=read();
	for (int pp=1; pp<=m; pp++)
	{
		memset(dr,0,sizeof(dr));
		memset(ans,0,sizeof(ans));
		memset(head1,0,sizeof(head1));
		q.clear();
		
		k=read();
		for (int j=1; j<=k; j++)//二次排序+lca连边 
		{
			int li;
			li=read();
			dr[li]=1;
			q.push_back(li);
		}
		
		sort(q.begin(),q.end(),cmp);
		
		int nde=q.size();
		for (int i=1; i<nde; i++) q.push_back(lca(q[i-1],q[i]));
		q.push_back(1);
		
		sort(q.begin(),q.end(),cmp);
		q.erase(unique(q.begin(),q.end()),q.end());
		
		int dba=q.size();
		for (int i=1;i<dba; i++)
		{
			int ll=lca(q[i-1],q[i]);
			add2(ll,q[i],ww);
		}
		dfs2(1,0);//树形dp 
		
		write(ans[1]);
		printf("\n");
	}
}
2025/8/2 09:13
加载中...