TLE 80求助
查看原帖
TLE 80求助
556362
Unnamed114514楼主2023/10/28 16:11
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N=1e6+5;
int n,m,k,K,tot,dep[N],son[N],dfn[N],top[N],c[N<<1],siz[N],fa[N],cnt[N],ans2,ans3,f[N][4];
ll ans1;
bool flg[N];
vector<int > G1[N],G2[N];
bool vis[N];
void dfs1(int u){
	siz[u]=1;
	for(auto v:G1[u]){
		if(v==fa[u]) continue;
		fa[v]=u,dep[v]=dep[u]+1,dfs1(v);
		if(siz[v]>siz[son[u]]) son[u]=v;	
	}
}
void dfs2(int u,int tp){
	dfn[u]=++tot,top[u]=tp;
	if(son[u]) dfs2(son[u],tp);
	for(auto v:G1[u]){
		if(v==fa[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}
inline int LCA(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]]) swap(u,v);
		v=fa[top[v]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	return u;
}
inline bool cmp(int a,int b){ return dfn[a]<dfn[b]; }
void dfs(int u){
	f[u][0]=f[u][1]=1e9,f[u][2]=f[u][3]=-1e9;
	if(flg[u]) f[u][0]=0,f[u][2]=0;
	for(auto v:G2[u]){
		int w=dep[v]-dep[u];
		if(vis[v]) continue;
		vis[v]=1;
		dfs(v);
		if(f[v][0]+w<f[u][0]) f[u][1]=f[u][0],f[u][0]=f[v][0]+w;
		else f[u][1]=min(f[u][1],f[v][0]+w);
		if(f[v][2]+w>f[u][2]) f[u][3]=f[u][2],f[u][2]=f[v][2]+w;
		else f[u][3]=max(f[u][3],f[v][2]+w);
		cnt[u]+=cnt[v];
		ans1+=1ll*cnt[v]*(K-cnt[v])*w;
	}
	ans2=min(ans2,f[u][0]+f[u][1]);
	ans3=max(ans3,f[u][2]+f[u][3]);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1,u,v;i<n;++i){
		cin>>u>>v;
		G1[u].push_back(v);
		G1[v].push_back(u);
	}
	dfs1(1),dfs2(1,1);
	cin>>m;
	while(m--){
		ans1=0,ans2=1e9,ans3=-1e9;
		cin>>k,K=k;
		for(int i=1;i<=k;++i) cin>>c[i],cnt[c[i]]=1,flg[c[i]]=1;
		stable_sort(c+1,c+k+1,cmp);
		for(int i=2;i<=K;++i) c[++k]=LCA(c[i-1],c[i]);
		stable_sort(c+1,c+k+1,cmp);
		for(int i=1;i<k;++i){
			int lca=LCA(c[i],c[i+1]);
			if(c[i]!=lca) G2[lca].push_back(c[i]);
			if(c[i+1]!=lca) G2[lca].push_back(c[i+1]);
		}
		dfs(c[1]);
		for(int i=1;i<=k;++i) G2[c[i]].clear(),G2[c[i]].shrink_to_fit(),cnt[c[i]]=0,vis[c[i]]=0,flg[c[i]]=0;
		cout<<ans1<<' '<<ans2<<' '<<ans3<<endl;
	}
	return 0;
}
2023/10/28 16:11
加载中...