Chasing Game

C++(g++ 7.5.0) 解法, 执行用时: 582ms, 内存消耗: 40468K, 提交时间: 2023-06-06 11:29:43

#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
const int M = 400010;
int n, m;
int head[N], pre[M], ver[M], tot;
void add(int x,int y){
    ver[++tot]=y; pre[tot]=head[x]; head[x]=tot;
}
int fa[N][22], dep[N];
void dfs(int x,int f){
    for (int i=1;i<=20;++i) fa[x][i]=fa[fa[x][i-1]][i-1];
    for (int i=head[x]; i; i=pre[i]){
        int v=ver[i];
        if (v==f) continue;
        fa[v][0]=x; dep[v]=dep[x]+1;
        dfs(v,x);
    }
}
int lca(int x,int y){
    if (dep[x]<dep[y]) swap(x,y);
    for (int i=20;i>=0;--i){
        if (dep[fa[x][i]]>=dep[y]) x=fa[x][i];
    }
    if (x==y) return x;
    for (int i=20;i>=0;--i){
        if (fa[x][i]!=fa[y][i]) x=fa[x][i], y=fa[y][i];
    }
    return fa[x][0];
}
int getdis(int x,int y){return dep[x]+dep[y]-2*dep[lca(x,y)];}
int getfa(int x,int k){
    for (int i=20;i>=0;--i){
        if (k>>i&1) x=fa[x][i];
    }
    return x;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1;i<n;++i){
        int x,y; cin>>x>>y;
        add(x,y); add(y,x);
    }
    dep[1]=1; dfs(1,0);
    while(m--){
        int x,y,z; cin>>x>>y>>z;
        int t=(getdis(x,z)+1)/2, p;
        int l=lca(x,z);
        if (dep[x]-dep[l]>=t) p=getfa(x,t);
        else p=getfa(z,getdis(x,z)-t);
//        printf("p=%d t=%d\n",p,t);
        int anst, ansp;
        if (getdis(x,p)+getdis(y,p)==getdis(x,y)){
            anst=max(getdis(x,p),getdis(z,p));
            ansp=p;
        }
        else anst=getdis(z,y), ansp=y;
        printf("%d %d\n",anst,ansp);
    }
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 794ms, 内存消耗: 41248K, 提交时间: 2023-07-06 21:18:06

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int f[N][22], d[N];
vector<int> g[N];

void dfs(int u, int fa) {
	d[u] = d[fa] + 1;
	for (int i = 1; i <= 20; i++) {
		f[u][i] = f[f[u][i - 1]][i - 1];
	}
	for (auto v : g[u]) {
		if (v == fa) continue;
		f[v][0] = u;
		dfs(v, u);
	}
}

int lca(int a, int b) {
	if (d[a] < d[b]) swap(a, b);
	for (int i = 20; i >= 0; i--) {
		if (d[f[a][i]] >= d[b]) a = f[a][i];
	}
	if (a == b) return a;
	for (int i = 20; i >= 0; i--) {
		if (f[a][i] != f[b][i]) {
			a = f[a][i];
			b = f[b][i];
		}
	}
	return f[a][0];
}

int dis(int a, int b) {
	return d[a] + d[b] - 2 * d[lca(a, b)];
}

int jump(int x, int distance) {
	for (int i = 0; i <= 20; i++) {
		if (distance >> i & 1) {
			x = f[x][i];
		}
	}
	return x;
}

int get(int a, int b, int distance) {
	int LCA = lca(a, b);
	int len = dis(a, b);
	if (d[a] - d[LCA] >= distance) {
		return jump(a, distance);
	} else {
		return jump(b, len - distance);
	}
}

int main() {

	cin.tie(nullptr)->ios::sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1, 0);
	while (q--) {
		int a, b, c;
		cin >> a >> b >> c;
		int dac = dis(a, c), dbc = dis(b, c), dab = dis(a, b);
		if (dab < dbc) {
            cout << max(dab, dbc) << ' ' << b << '\n';
        } else {
            cout << (dac + 1) / 2 << ' ' << get(a, c, (dac + 1) / 2) << '\n';
        }
	}


	return 0;
}

详情