@Chilling
2017-02-18T15:42:09.000000Z
字数 2751
阅读 942
LCA
Description
You are given a tree (an undirected acyclic connected graph) with N nodes, and edges numbered 1, 2, 3...N-1. Each edge has an integer value assigned to it, representing its length.
We will ask you to perfrom some instructions of the following form:
Path from node 4 to node 6 is 4 -> 2 -> 1 -> 3 -> 6
DIST 4 6 : answer is 5 (1 + 1 + 1 + 2 = 5)
KTH 4 6 4 : answer is 3 (the 4-th node on the path from node 4 to node 6 is 3)
Input
The first line of input contains an integer t, the number of test cases (t <= 25). t test cases follow.
For each test case:
Output
For each "DIST" or "KTH" operation, write one integer representing its result.
Print one blank line after each test.
Example
Input
1
6
1 2 1
2 4 1
2 5 2
1 3 1
3 6 2
DIST 4 6
KTH 4 6 4
DONE
Output
5
3
题意: t组数据,给出一个无向图,DIST询问两点之间的距离,KTH询问两点之间的第k个点,DONE结束。
分析: 两点在图上的距离,连线一定经过他们的最近公共祖先(LCA),因此两点之间的距离即为
dis[u]+dis[v]-2*dis[LCA(u,v)]
;
找u,v之间的第k个点,首先要知道该点是在LCA(u,v)的左边还是右边,然后以u点或者v点向上倍增得到第k个点。
为什么不以LCA(u,v)向下找?向下可能会遇到很多分支,而以一点向上找只有一条路径。
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
#define maxn 10005
using namespace std;
int n;
int dep[maxn]; //深度
int dis[maxn];
int fa[maxn][15];//2^14>10000,各点向上跳2^i到达的点
struct node
{
int en,val;
node(int enn=0,int vall=0)
{
en=enn;
val=vall;
}
};
vector<node> V[maxn];
void clr()
{
memset(dep,0,sizeof(dep));
memset(dis,0,sizeof(dis));
memset(fa,0,sizeof(fa));
for(int i=0;i<=n;i++)
V[i].clear();
}
void dfs(int u,int f,int d)//深度
{
fa[u][0]=f;
for(int i=1;i<15;i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
dep[u]=d;
for(int i=0;i<V[u].size();i++)
{
node v=V[u][i];
if(v.en==f) continue;
dis[v.en]=dis[u]+v.val;
dfs(v.en,u,d+1);
}
}
int LCA(int u,int v)
{
if(dep[u]>dep[v])
swap(u,v); //u浅v深
for(int i=0;i<15;i++) //使等深度
if((dep[v]-dep[u])>>i&1)
v=fa[v][i];
if(u==v) return u;
for(int i=14;i>=0;i--) //同时向上跳
{
if(fa[u][i]!=fa[v][i])
{
u=fa[u][i];
v=fa[v][i];
}
}
return fa[u][0];
}
int kth(int u,int v,int k)
{
int ans;
int lca=LCA(u,v);
int cnt=dep[u]+dep[v]-2*dep[lca]+1; //u到v数字个数
if(dep[u]-dep[lca]+1==k)
return lca;
else if(dep[u]-dep[lca]+1<k)//在lca右边
{
k=cnt-k;//跳的步数
u=v;
}
else k--;//左边
for(int i=0;i<15;i++)
if(k&(1<<i))
u=fa[u][i];
return u;
}
int main()
{
int t;
int a,b,c;
char s[9];
scanf("%d",&t);
while(t--)
{
clr();
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&a,&b,&c);
V[a].push_back(node(b,c));
V[b].push_back(node(a,c));
}
dfs(1,0,1);
while(1)
{
scanf("%s",s);
if(s[1]=='I')
{
scanf("%d%d",&a,&b);
printf("%d\n",dis[a]+dis[b]-2*dis[LCA(a,b)]);
}
else if(s[1]=='T')
{
int ans;
scanf("%d%d%d",&a,&b,&c);
printf("%d\n",kth(a,b,c));
}
else break;
}
}
return 0;
}