给出思路,求大佬调代码
查看原帖
给出思路,求大佬调代码
786781
wdsjl楼主2024/9/10 21:14

不被抓到要有如下条件:

  1. 有一个度数大于等于3的点
  2. 并且躲的人能在抓的人之前来到这个点
  3. 与这个点相连的长度大于等于2的路至少有3条
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+10;

long long d[N],h[N],tot,t,n,p,q,maxxd,ds[N],vis[N],d1,d2,re,cnt;

struct node{
	int to,ne;
}e[N];

void add(int x,int y){
	e[++tot]={y,h[x]};
	h[x]=tot;
	return ;
}

void dfs(int cur){
	vis[cur]++;
//	if(re==cur){
//		re=cur;
//		return ;
//	}
	for(int i=h[cur];i;i=e[i].ne){
		int y=e[i].to;
		if(vis[y])continue;
		ds[y]=ds[cur]+1;
		dfs(y);
	}
	return ;
}

int main(){
	scanf("%d",&t);
	while(t--){
		int boo=0;
		memset(d,0,sizeof(d));
		memset(h,0,sizeof(h));
		tot=0;
		scanf("%d%d%d",&n,&p,&q);
		for(int i=1;i<n;i++){
			int x,y;
			scanf("%d%d",&x,&y);
			add(x,y);
			add(y,x);
			d[x]++;
			d[y]++;
			maxxd=max(maxxd,max(d[x],d[y]));
		}
		for(int i=1;i<=n;i++){
			if(d[i]>=3){
					re=i;
					memset(vis,0,sizeof(vis));
					memset(ds,0,sizeof(ds));
					dfs(re);
					d1=ds[p];
					d2=ds[q];
					for(int i=1;i<=n;i++){
						if(ds[i]>=2)cnt++;
					}
					if(d1-d2>1&&cnt>2){
						printf("Drifty\n");
						boo=1;
					}
			}
		}
		if(boo==0){
			printf("hgcnxn\n");
		}
	}
	return 0;
}
2024/9/10 21:14
加载中...