洛谷P4281（AHOI2008）-紧急集合(LCA)

Rowena ·

更新时间:2024-11-11

· 682 次阅读

题意：

在一颗 n 个节点的树上，有 q 个询问，每次询问给出x 、 y 、 z 三个节点，要求在树上找到一个点 ppp，使得 distance=dist(x,p)+dist(y,p)+dist(z,p)distance = dist(x,p) + dist(y,p) + dist(z,p)distance=dist(x,p)+dist(y,p)+dist(z,p) 取得最小值;

思路:

最佳集合点 p只能是LCA(x,y),LCA(y,z),LCA(x,z)p 只能是 LCA(x,y),LCA(y,z),LCA(x,z)p只能是LCA(x,y),LCA(y,z),LCA(x,z) 三者其中之一

证明：证明：证明：

当只有两个点 x，yx，yx，y 时，只要 ppp 在 x 到 y的路径上，dist(p,x)+dist(p,y)dist(p,x)+dist(p,y)dist(p,x)+dist(p,y)，假设集合点一定在 xxx 到 yyy 的路径上。如今再加入 zzz 点，要做的是让 dist(p,z)dist(p,z)dist(p,z) 尽量小，设 k=LCA(x,y)k = LCA(x,y)k=LCA(x,y) 。
当 zzz 不在 kkk 的子树下时，集合点应该选 kkk 即LCA(x,y)；LCA(x,y)；LCA(x,y)；
当 zzz 在 kkk 的子树下时，分为两种情况：
① zzz 在 xxx 或 yyy 的子树下，那么集合点就应该选 xxx 或 yyy 即 LCA(x,z)和LCA(y,z)；LCA(x,z)和LCA(y,z)；LCA(x,z)和LCA(y,z)；
② zzz 不在 xxx 的子树下且不在 yyy 的子树下时，集合点应该选 kkk 即LCA(x,y)；LCA(x,y)；LCA(x,y)；
综上所述，ppp 只可以取LCA(x,y)，LCA(y,z)，LCA(x,z)LCA(x,y)，LCA(y,z)，LCA(x,z)LCA(x,y)，LCA(y,z)，LCA(x,z)

再回到一开始，ppp 点有没有可能不在 xxx 到 yyy 的路径上会使得 distancedistancedistance 更小呢？
答案是不可能，画颗树可以知道：
如果 zzz 在 xxx 到 yyy 这条链上，集合点就在链的中间那个点上，这个点显然在链上
如果 zzz 不在这条链上，如果让集合点去靠近 zzz 目的来缩小 dist(z,p)dist(z,p)dist(z,p) ，xxx 和 yyy 都会以两倍的奉还

因此我们可以知道最佳集合点 ppp 应该在 x,y,zx,y,zx,y,z 任意两点的路径上，即在路径 x−>yx->yx−>y ，x−>zx->zx−>z ,y−>zy - > zy−>z，就是这三条路径的交点就是最佳集合点

另外这题用倍增似乎要开O2 和用快读才能过，而且听说会卡 TarjanTarjanTarjan 有空补下树剖

#pragma GCC optimize(2)
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 5e5+10;
int n,q,head[N],idx;
pair ans;
struct Node{
	int to,nex;
}e[N<<1];
int read() {
    int s = 0; bool f = false; char c = getchar();
    while (c  '9') f |= (c == '-'), c = getchar();
    while (c >= '0' && c <= '9') s = (s << 3) + (s << 1) + (c ^ 48), c = getchar();
    return f ? -s : s;
}
void add_edge(int u,int v){
	e[idx].to = v;
	e[idx].nex = head[u];
	head[u] = idx++;
}
int dep[N],fa[N][20];
void dfs(int u,int f){
	dep[u] = dep[f] + 1;
	fa[u][0] = f;
	for(int i = head[u];~i;i = e[i].nex){
		if(e[i].to != f){
			dfs(e[i].to,u);
		}
	}
}
void init(){
	for(int k = 1;(1<<k) <= n;k++){
		for(int i = 1;i <= n;i++){
			fa[i][k] = fa[fa[i][k-1]][k-1];
		}
	}
}
int lca(int u,int v){
	if(dep[u] = 0;i--){
			if(dep[fa[u][i]] >= dep[v]) u = fa[u][i];
		}
	}
	if(u == v) return u;
	for(int i = 19;i >= 0;i--){
		if(fa[u][i] != fa[v][i]){
			u = fa[u][i],v = fa[v][i];
		}
	}
	return fa[u][0];
}
void cal(int x,int y,int z){
	int lca1 = lca(x,y);
	int distance = dep[x]+dep[y]-2*dep[lca1];
	int lca2 = lca(lca1,z);
	distance += dep[lca1]+dep[z]-2*dep[lca2];
	if(ans.second > distance){
		ans.first = lca1;
		ans.second = distance;
	}
}
int main(){
	n = read();q = read();
	//scanf("%d%d",&n,&q);
	memset(head,-1,sizeof(head));
	for(int i = 1;i < n;i++){
		int u,v;
		u = read(),v = read(); 
		//scanf("%d%d",&u,&v);
		add_edge(u,v);add_edge(v,u);
	}
	dfs(1,0);
	init();
	while(q--){
		int x,y,z;
		x = read(),y = read(),z = read();
		//scanf("%d%d%d",&x,&y,&z);
		int u = lca(x,y);
		ans.first = -1,ans.second = inf;
		cal(x,y,z);cal(x,z,y);cal(y,z,x);
		printf("%d %d\n",ans.first,ans.second);
	}
	return 0;
}