在一颗 n 个节点的树上,有 q 个询问,每次询问给出x 、 y 、 z 三个节点,要求在树上找到一个点 最佳集合点 当只有两个点 再回到一开始, 因此我们可以知道最佳集合点 另外这题用倍增似乎要开O2 和用快读才能过,而且听说会卡
题意:
p,使得
distance=dist(x,p)+dist(y,p)+dist(z,p) 取得最小值;思路:
p只能是LCA(x,y),LCA(y,z),LCA(x,z) 三者其中之一
证明:
x,y 时,只要
p 在 x 到 y的路径上,
dist(p,x)+dist(p,y),假设集合点一定在
x 到
y 的路径上。如今再加入
z 点,要做的是让
dist(p,z) 尽量小,设
k=LCA(x,y) 。
当
z 不在
k 的子树下时,集合点应该选
k 即
LCA(x,y);
当
z 在
k 的子树下时,分为两种情况:
①
z 在
x 或
y 的子树下,那么集合点就应该选
x 或
y 即
LCA(x,z)和LCA(y,z);
②
z 不在
x 的子树下且不在
y 的子树下时,集合点应该选
k 即
LCA(x,y);
综上所述,
p 只可以取
LCA(x,y),LCA(y,z),LCA(x,z)
p 点有没有可能不在
x 到
y 的路径上会使得
distance 更小呢?
答案是不可能,画颗树可以知道:
如果
z 在
x 到
y 这条链上,集合点就在链的中间那个点上,这个点显然在链上
如果
z 不在这条链上,如果让集合点去靠近
z 目的来缩小
dist(z,p) ,
x 和
y 都会以两倍的奉还
p 应该在
x,y,z 任意两点的路径上,即在路径
x−>y ,
x−>z ,
y−>z,就是这三条路径的交点就是最佳集合点
Tarjan 有空补下树剖#pragma GCC optimize(2) #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const int N = 5e5+10; int n,q,head[N],idx; pair<int,int> ans; struct Node{ int to,nex; }e[N<<1]; int read() { int s = 0; bool f = false; char c = getchar(); while (c < '0' || 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] < dep[v]) swap(u,v); if(dep[u] != dep[v]){ for(int i = 19;i >= 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 %dn",ans.first,ans.second); } return 0; }
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算
官方软件产品操作指南 (170)