跪求查错,调了一天8h了
查看原帖
跪求查错,调了一天8h了
684254
Rain_chr楼主2023/1/29 17:14
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	int ans=0,f=1;
	char x=getchar();
	while(x<'0'||x>'9')
	{
		if(x=='-')
			f=-f;
		x=getchar();
	}
	while(x<='9'&&x>='0')
	{
		ans=(ans<<3)+(ans<<1)+(x^48);
		x=getchar();
	}
	return ans*f;
}
const int N=3e5+10;
int n,m,cnt;
vector<int> a[N];
vector<int> g[N];
int dfn[N];
int d[N],f[N][20];
int pos[N],dis[N]; 
int sum[N];
void dfs(int x,int fa)
{
	dfn[x]=++cnt;
	f[x][0]=fa;
	sum[x]=1;
	for(int i=0;i<a[x].size();i++)
	{
		int son=a[x][i];
		if(son==fa)
			continue;
		d[son]=d[x]+1;
		dfs(son,x);
		sum[x]+=sum[son];
	}
}
void init()
{
	for(int i=1;(1<<i)<=n;i++)
		for(int j=1;j<=n;j++)
			f[j][i]=f[f[j][i-1]][i-1];
}
int LCA(int x,int y)
{
	if(d[x]<d[y])
		swap(x,y);
	for(int i=log2(n);i>=0;i--)
		if(d[f[x][i]]>=d[y])
			x=f[x][i];
	if(x==y)
		return x;
	for(int i=log2(n);i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
struct Stack
{
	int st[N],tp;
	void push(int x)
	{
		st[++tp]=x;
	}
	void pop()
	{
		tp--;
	}
	void clear()
	{
		tp=0;
	}
	int top()
	{
		return st[tp];
	}
	int next()
	{
		return st[tp-1];
	}
	int size()
	{
		return tp;
	}
}s;
void insert(int x)
{
	if(!s.size())
	{
		s.push(x);
		return ;
	}
	int k=LCA(x,s.top());
	while(s.size()>1&&d[s.next()]>=d[k])
	{
		g[s.next()].push_back(s.top());
		s.pop();
	}
	if(d[k]<d[s.top()])
	{
		g[k].push_back(s.top());
		s.pop();
	}
	if(s.size()==0||s.top()!=k)
		s.push(k);
	s.push(x);
}
vector<int> key,per;
bool is[N];
int ans[N];
bool cmp(int x,int y)
{
	return dfn[x]<dfn[y];
}
int dist(int x,int y)
{
	return d[x]+d[y]-2*d[LCA(x,y)];
}
void dfs2(int x)
{
	dis[x]=pos[x]=1e9;
	for(int i=0;i<g[x].size();i++)
	{
		int son=g[x][i];
		dfs2(son);
		if(dis[son]+dist(x,son)<dis[x])
		{
			dis[x]=dis[son]+dist(x,son);
			pos[x]=son;
		}
		else if(dis[son]+dist(x,son)==dis[x]&&son<pos[x])
			pos[x]=son;
	}
	if(is[x])
		pos[x]=x,dis[x]=0,is[x]=0;
}
void dfs3(int x)
{
	for(int i=0;i<g[x].size();i++)
	{
		int son=g[x][i];
		if(dis[son]>dis[x]+dist(x,son))
		{
			dis[son]=dis[x]+dist(x,son);
			pos[son]=pos[x];
		}
		else if(dis[son]==dis[x]+dist(x,son)&&pos[son]>pos[x])
			pos[son]=pos[x];
		dfs3(son);
	}
}
int find(int x,int y)
{
	for(int i=log2(n);i>=0;i--)
		if(d[f[y][i]]>d[x])
			y=f[y][i];
	return y;
}
int area(int x,int y)
{
	for(int i=log2(n);i>=0;i--)
		if(d[x]<d[f[y][i]])
			if(dist(x,f[y][i])>dist(y,f[y][i])||dist(x,f[y][i])==dist(y,f[y][i])&&pos[x]>pos[y])
				y=f[y][i];
	return y;
}
void dfs4(int x)
{
	for(int i=0;i<g[x].size();i++)
	{
		int son=g[x][i];
		ans[pos[x]]-=sum[find(x,son)];
		int k=area(x,son);
		ans[pos[son]]+=sum[k]-sum[son];
		ans[pos[x]]+=sum[find(x,son)]-sum[k];
	}
	ans[pos[x]]+=sum[x];
	for(int i=0;i<g[x].size();i++) 
		dfs4(g[x][i]);
}
void dfs5(int x)
{
	for(int i=0;i<g[x].size();i++)
		dfs5(g[x][i]);
	ans[x]=0;
	g[x].clear();
}
signed main()
{
//	freopen("1.in","r",stdin);
//	freopen("mine.out","w",stdout);
	n=read();
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		a[x].push_back(y);
		a[y].push_back(x);
	}
	d[1]=1;
	dfs(1,0);
	init(); 
	int m=read();
	for(int i=1;i<=m;i++)
	{
		key.clear();
		per.clear(); 
		s.clear();
		int x=read();
		for(int j=1;j<=x;j++)
		{
			key.push_back(read());
			is[key[j-1]]=1;
			per.push_back(key[j-1]);
		}
		sort(key.begin(),key.end(),cmp);
		if(key[0]!=1)
			insert(1);
		for(int j=0;j<x;j++)
			insert(key[j]);
		while(s.size()>1)
			g[s.next()].push_back(s.top()),s.pop();
		dfs2(1);
		dfs3(1);
		dfs4(1);
		for(int j=0;j<x;j++)
			printf("%lld ",ans[per[j]]);
		putchar('\n');
		dfs5(1);
	}
	return 0;
}
2023/1/29 17:14
加载中...