倍增 10pts 求条
查看原帖
倍增 10pts 求条
1268478
時空楼主2024/8/20 19:57

RT

#include <bits/stdc++.h>

#define FstIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pb push_back
#define mem(a, v) memset(a, v, sizeof a)
#define pii pair<ll, ll>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
 
const ll N = 2e6 + 5, M = 5e2 + 5;
const ll mod = 1e9 + 7, mod2 = 998244353;
const ld eps = 1e-6;

ll d, t;

ll n, q;

ll h[N], edge;

struct dge
{
	ll nx, to;
}E[N];

void add(ll u, ll v) { E[++ edge] = {h[u], v}; h[u] = edge; }

ll depth[N], Jp[N][32];

void dfs(ll u, ll father)
{
	for (ll i = h[u]; i; i = E[i].nx)
	{
		ll j = E[i].to;
		if (j == father) continue;
		depth[j] = depth[u] + 1;
		Jp[j][0] = u;
		dfs(j, u);
	}
}

void PreForJump()
{
	for (ll k = 1; k <= 30; ++ k )
		for (ll i = 1; i <= n; ++ i )
			Jp[i][k] = Jp[Jp[i][k - 1]][k - 1];
}

ll LCA(ll x, ll y)
{
//	if (x == y) return x;
	if (depth[x] < depth[y]) swap(x, y);
	for (ll k = 30; ~k; -- k )
	{
		if (depth[Jp[x][k]] >= depth[y]) x = Jp[x][k];
	}
	if (x == y) return x;
	for (ll k = 30; ~k; -- k )
	{
		if (depth[Jp[x][k]] != depth[Jp[y][k]]) x = Jp[x][k], y = Jp[y][k];
	}
	return Jp[x][0];
}

ll dist(ll x, ll y)
{
	return depth[x] + depth[y] - 2 * depth[LCA(x, y)];	
}

signed main()
{
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	
	cin >> d >> t;
	while (t -- )
	{
		cin >> n >> q;
		edge = 0;
		for (ll i = 0; i <= n; ++ i ) h[i] = depth[i] = 0;
		
		for (ll i = 0; i <= n; ++ i )
			for (ll k = 0; k <= 30; ++ k )
			Jp[i][k] = 0;
				
		for (ll i = 1; i < n; ++ i )
		{
			ll u, v; cin >> u >> v;
			add(u, v); add(v, u);
		}
		dfs(1, 1);
		PreForJump();
		while (q -- )
		{
			ll a, b, da, db, ds;
			cin >> a >> b >> da >> db;
			ds = dist(a, b);
			if (ds <= da) cout << "Zayin\n";
			else if (da < db) cout << "Ziyin\n";
			else if (da > db) cout << "Zayin\n";
			else cout << "Draw\n";
		}
	}
	
	
	return 0;
	
	cout.flush();
}
2024/8/20 19:57
加载中...