没有全清空,没有把原树和虚树写反,TLE4个点
查看原帖
没有全清空,没有把原树和虚树写反,TLE4个点
979656
Sgt_Dante楼主2024/12/7 22:40

RT

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
#define int ll
#define endl '\n'
const int N=5e5+5,M=4e5+5;
const int MOD=998244353;

int n,q;
int h[N],e[N*2],ne[N*2],idx,ct[N*2];
int dep[N],dfn[N],fth[33][N];
int dp[N],tim,m,ord[N],fr[N];
vector<int> G[N];
bool ask[N];

void add(int u,int v,int w)
{
	ct[idx]=w,e[idx]=v,ne[idx]=h[u],h[u]=idx++;
}

void dfs(int u,int fa)
{
	dfn[u]=++tim,ord[tim]=u;
	dep[u]=dep[fa]+1,fth[0][u]=fa;
	for(int i=1;i<32;i++)
		fth[i][u]=fth[i-1][fth[i-1][u]];
	for(int i=h[u];~i;i=ne[i])
	{
		int v=e[i];
		if(v==fa) continue;
		fr[v]=min(fr[u],ct[i]);
		dfs(v,u);
	}
	return ;
}

int lca(int a,int b)
{
	if(dep[a]<dep[b]) swap(a,b);
	for(int i=32;i>=0;i--)
		if(dep[fth[i][a]]>=dep[b])
			a=fth[i][a];
	if(a==b) return a;
	for(int i=32;i>=0;i--)
	{
		if(fth[i][a]!=fth[i][b])
			a=fth[i][a],b=fth[i][b];
	}
	return fth[0][a];
}

void ddfs(int u,int fa)
{
	dp[u]=0;
	for(auto v:G[u])
	{
		int w=fr[v];
		if(v==fa) continue;
		ddfs(v,u);
		if(ask[v]) dp[u]+=w;
		else dp[u]+=min(dp[v],w);
	}
	return ;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	memset(h,-1,sizeof h);
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	fr[1]=1e18;
	dfs(1,0);
//	for(int i=1;i<=n;i++) cout<<fr[i]<<" ";
//	cout<<endl;
	cin>>m;
	vector<pii> pos;
	while(m--)
	{
		int k;
		pos.clear();
		pos.push_back({1,1});
		cin>>k;
		for(int i=1;i<=k;i++)
		{
			int u;cin>>u;ask[u]=1;
			pos.push_back({dfn[u],u});
		}
		sort(pos.begin(),pos.end());
		for(int i=1;i<=k;i++)
		{
			int nu=lca(pos[i].second,pos[i-1].second);
			pos.push_back({dfn[nu],nu});
		}
		sort(pos.begin(),pos.end());
		int len=unique(pos.begin(),pos.end())-pos.begin();
		for(int i=1;i<len;i++)
		{
			int v=pos[i].second,u=lca(pos[i].second,pos[i-1].second);
			G[u].push_back(v);
		}
		ddfs(1,0);
		for(int i=0;i<len;i++)
			ask[pos[i].second]=0,G[pos[i].second].clear();
		cout<<dp[1]<<endl;
	}
	return 0;
}
2024/12/7 22:40
加载中...