10 pts 求助
查看原帖
10 pts 求助
987758
CaoSheng_zzz楼主2024/10/10 08:57
#include <cmath>
#include <stdio.h>
#include <iostream>

const int maxn = 1e6 + 1;
int n , q ;
int h[maxn] , cnt ;
int anc[maxn][21] , dis[maxn] ;
struct edge {
	int next , to ;
} e[maxn << 1];

void add(int u , int v) { e[++ cnt] = {h[u] , v} ; h[u] = cnt ;}

void dfs(int u , int fa) {
	dis[u] = dis[fa] + 1 , anc[u][0] = fa ;
	for(int i=1 ; (1<<i)<=dis[u] ; i++) anc[u][i] = anc[anc[u][i - 1]][i - 1] ;
	for(int i=h[u] ; i ; i=e[i].next) {
		int v = e[i].to ;
		if(v != fa) dfs(v , u) ;
	}
}

int lca(int a , int b) {
	if(dis[a] < dis[b]) std::swap(a , b) ;
	int k = log2(a) / log(2) ;
	for(int i=k ; i>=0 ; i--) {
		if(dis[a] - (1 << i) >= dis[b]) a = anc[a][i] ;
	}
	if(a == b) return a ;
	for(int i=k ; i>=0 ; i--) {
		if(anc[a][i] != anc[b][i]) a = anc[a][i] , b = anc[b][i] ;
	}
	return anc[a][0] ;
}

void init(int n) {
	for(int i=1 ; i<=n ; i++) {
		h[i] = dis[i] = 0 ;
		e[i] = e[i + n] = {0 , 0} ;
		for(int j=0 ; (1<<j)<=n ; j++) anc[i][j] = 0 ;
	}
	cnt = 0 ;
}

void Solve() {
	scanf("%d%d" , &n , &q) ; init(n) ;
	for(int i=1 ; i<n ; i++) {
		int u , v ;
		scanf("%d%d" , &u , &v) ;
		add(u , v) ;
		add(v , u) ;
	}
	dfs(1 , 0) ;
	while(q --) {
		int a , b , da , db ;
		scanf("%d%d%d%d" , &a , &b , &da , &db) ;
		int o = lca(a , b) ;
		int dist = dis[a] + dis[b] - dis[o] * 2 ;
		if(da >= dist) puts("Zayin") ;
		else if(da > db) puts("Zayin") ;
		else if(da == db) puts("Draw") ;
		else puts("Ziyin") ;
	}
	return ;
}

signed main() {
	int _T , T ; scanf("%d%d" , &_T , &T) ;
	while(T --) Solve() ;
	return 0 ;
}
2024/10/10 08:57
加载中...