P10076 90pts TLE 求调
查看原帖
P10076 90pts TLE 求调
1064579
huhaoming2011楼主2024/11/25 13:05
#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e6+1000;
int hd[MAXN],nxt[MAXN],to[MAXN],f[MAXN][30],dep[MAXN],fnn[MAXN][30];
int d,T,n,q,cnt,maxn;
bool vis[MAXN];

void add(int u,int v)
{
	++cnt;
	to[cnt]=v;
	nxt[cnt]=hd[u];
	hd[u]=cnt;
}

void dfs(int x,int fa)
{
	vis[x]=true;
	for(int i=1;i<=log2(n);i++)
	{
		f[x][i]=f[f[x][i-1]][i-1];
		fnn[x][i]=fnn[f[x][i-1]][i-1]+fnn[x][i-1]; 
	}
	for(int i=hd[x];i;i=nxt[i])
	{
		if(vis[to[i]])
		{
			continue ;
		}
		dep[to[i]]=dep[x]+1;
		f[to[i]][0]=x;
		fnn[to[i]][0]=1;
		dfs(to[i],x);
	}
	return ;
}

int main()
{
//	freopen("game.in","r",stdin);
//	freopen("game.out","w",stdout);
	scanf("%d%d",&d,&T);
	int u,v;
	for(int i=1;i<=T;i++)
	{
		cnt=0;
		scanf("%d%d",&n,&q);
	//	maxn=max(maxn,n);
		
		for(int j=1;j<n;j++)
		{
			scanf("%d%d",&u,&v);
			add(u,v);
			add(v,u);
		}
		dep[1]=1;
		dfs(1,0);
//		for(int j=1;j<=n;j++)
//		{
//			for(int c=1;c<=log2(n);c++)
//			{
//				f[j][c]=f[f[j][c-1]][c-1];
//				fnn[j][c]=fnn[f[j][c-1]][c-1]+fnn[j][c-1]; 
//			}
//		}
	//	cout<<f[2][0]<<endl;
		for(int j=1;j<=q;j++)
		{
			int s,t,da,db,lca=0;
			long long sum=0;
			scanf("%d%d%d%d",&s,&t,&da,&db);
			if(dep[s]<dep[t])swap(s,t);
			for(int c=log2(n);c>=0;c--)
			{
				if(dep[f[s][c]]>=dep[t])
				{
					sum+=fnn[s][c];
					s=f[s][c];
				}
			}
		//	cout<<"dep:"<<dep[s]<<" "<<dep[t]<<endl;
		//	cout<<s<<" "<<t<<endl;
			if(s!=t)
			{
				for(int c=log2(n);c>=0;c--)
				{
					if(f[s][c]!=f[t][c])
					{
						sum+=fnn[s][c]+fnn[t][c];
						s=f[s][c];
						t=f[t][c];
					}
				}
				sum+=fnn[s][0]+fnn[t][0];
			}
			
		//	cout<<s<<"    "<<sum<<endl;
			if(sum<=da||da>db)
			{
				printf("Zayin\n");
			}
			else if(da==db)
			{
				printf("Draw\n");
			}
			else
			{
				printf("Ziyin\n");
			}
		}
		for(int j=0;j<=n;j++)
		{
			hd[j]=0,hd[j*2]=0;
			vis[j]=false,dep[j]=0;
			for(int k=0;k<=log2(n);k++)
			{
				f[j][k]=fnn[j][k]=f[j][k]=fnn[j][k]=0;
			}
		}
	}
//	cout<<maxn;
	return 0;
}
2024/11/25 13:05
加载中...