蒟蒻刚学虚数0.1秒,求调30分代码
查看原帖
蒟蒻刚学虚数0.1秒,求调30分代码
532109
freedom_wang楼主2024/5/5 21:43
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rop(i,a,b) for(int i=a;i<b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define por(i,a,b) for(int i=a;i>b;i--)
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double ld;
using namespace std;
struct edge{
	int to,nxt;
}e[2000005];
int n,q,tot,head[1000005],u,v,id,top,dep[1000005],dp[1000005][25],dfn[1000005],siz[1000005],k,h[1000005],stk[1000005],g[1000005],mn[1000005],mx[1000005],cnt,totans,minans,maxans;
bool tag[1000005];
bool cmp(int a,int b){
	return dfn[a]<dfn[b];
}
void add(int u,int v){
	e[++tot].to=v;
	e[tot].nxt=head[u];
	head[u]=tot;
}
void dfs(int u,int fa){
	dep[u]=dep[fa]+1;
	dp[u][0]=fa;
	dfn[u]=++id;
	rep(i,1,20)
		dp[u][i]=dp[dp[u][i-1]][i-1];
	for(int i=head[u];i;i=e[i].nxt){
		int to=e[i].to;
		if(to==fa)
			continue;
		dfs(to,u);
	}
}
int lca(int u,int v){
	if(dep[u]<dep[v])
		swap(u,v);
	per(i,20,0)
		if(dep[dp[u][i]]>=dep[v])
			u=dp[u][i];
	if(u==v)
		return u;
	per(i,20,0)
		if(dp[u][i]!=dp[v][i]){
			u=dp[u][i];
			v=dp[v][i];
		}
	return dp[u][0];
}
void solve(int u){
	siz[u]=tag[u];
	g[u]=0;
	if(tag[u])
		mx[u]=mn[u]=0;
	else{
		mn[u]=2147483647;
		mx[u]=-2147483647;
	}
	for(int i=head[u];i;i=e[i].nxt){
		int to=e[i].to;
		solve(to);
		int l=dep[to]-dep[u];
		totans+=(g[u]+siz[u]*l)*siz[to]+g[to]*siz[u];
		siz[u]+=siz[to];
		g[u]+=g[to]+l*siz[to];
		minans=min(minans,mn[u]+mn[to]+l);
		maxans=max(maxans,mx[u]+mx[to]+l);
		mn[u]=min(mn[u],mn[to]+l);
		mx[u]=max(mx[u],mx[to]+l);
	}
}
signed main(){
// 	freopen("P4103_1.in","r",stdin);
// 	freopen("P4103_1(2).out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	rop(i,1,n){
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	dep[0]=0;
	dfs(1,0);
	cin>>q;
	while(q--){
		cin>>k;
		rep(i,1,k){
			cin>>h[i];
			tag[h[i]]=1;
		}
		sort(h+1,h+k+1,cmp);
		stk[top=1]=1;
		tot=0;
		head[1]=0;
		rep(i,1,k){
			if(h[i]!=1){
				int l=lca(h[i],stk[top]);
				if(l!=stk[top]){
					while(dfn[l]<dfn[stk[top-1]])
						add(stk[top--],stk[top+1]);
					if(dfn[l]==dfn[stk[top-1]])
						add(l,stk[top--]);
					else{
						head[l]=0;
						add(l,stk[top]);
						stk[top]=l;
					}
				}
				head[h[i]]=0;
				stk[++top]=h[i];
			}
		}
		rop(i,1,top)
			add(stk[i],stk[i+1]);
		totans=0;
		minans=2147483647;
		maxans=-2147483647;
		solve(1);
		cout<<totans<<' '<<minans<<' '<<maxans<<endl;
		rep(i,1,k)
			tag[h[i]]=0;
	}
	return 0;
}
/*

*/

悬2关

2024/5/5 21:43
加载中...