SPOJ 913 Query on a tree II (倍增)

Time limit 433 ms Memory limit 1572864kB Code length Limit 15000 B

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:

DIST a b : ask for the distance between node a and node b
or
KTH a b k : ask for the k-th node on the path from node a to node b
Example:
N = 6 
1 2 1 // edge connects node 1 and node 2 has cost 1 
2 4 1 
2 5 2 
1 3 1 
3 6 2 

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:

In the first line there is an integer N (N <= 10000)
In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of cost c (c <= 100000)
The next lines contain instructions "DIST a b" or "KTH a b k"
The end of each test case is signified by the string "DONE".
There is one blank line between successive tests.

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

题意：

有一棵树，给你两个点，求出这两个点间的距离和第k个点是多少
输出表示的意思：
第一行，输入一个数t；表示有k组数据
第二行，输入一个数n；表示这棵树有多少个点；
接下来n-1行，输入u，v,k这三个数，表示这n个点的关系，与对应u、v间的距离；
输入完成后，再输入指令；如果输入：DIST x，y表示求x与y之间的距离
输入 KTH x，y，k 表示求x到y的第k个节点是多少

解题思路：

利用倍增法求lca（最近公共祖先）x与y间的距离=dis[x]+dis[y]-2*dis[lca(x,y)];
而求第k个节点的位置可以转化为求x或y的父节点（这里又需要用倍增的方法）
具体怎样处理看代码

完整代码：

• 用vector

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
#define N 10010
int p[N][20];///p[i][j]表示i的第2^j倍祖先;
int dep[N];///表示深度
int dis[N];///表示要求两点之间的距离
int n;
struct node
{
    int w,l;
    node(int ww=0,int ll=0)
    {
        w=ww;
        l=ll;
    }
};
vector<node>g[N];
void dfs(int u,int f,int d)
{
    p[u][0]=f;
    dep[u]=d;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i].w;
        if(v==f)
            continue;
        dis[v]=dis[u]+g[u][i].l;
        dfs(v,u,d+1);
    }
}
void init()
{
    dfs(1,0,1);
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i<=n;i++)
            if(p[i][j]!=-1)
                p[i][j]=p[p[i][j-1]][j-1];///i的第2^j倍祖先=i的第2^(j-1)倍祖先的2^(j-1)倍祖先
}
int LCA(int u,int v)
{
    if(dep[u]>dep[v])
        swap(u,v);
    int i;
    for(i=0;(1<<i)<=dep[v];i++);
    for(int j=i-1;j>=0;j--)
        if(dep[v]-(1<<j)>=dep[u])
            v=p[v][j];
    if(u==v)
        return u;
    for(int j=i-1;j>=0;j--)
    {
        if(p[v][j]!=-1&&p[u][j]!=p[v][j])
        {
            u=p[u][j];
            v=p[v][j];
        }
    }
    return p[u][0];
}
//*写得很麻烦~~没得事~~你看得懂就好@_@*//
int kkk(int u,int v,int k)
{
    int lca=LCA(u,v);
    if(dep[u]-dep[lca]+1>=k)///说明第k个点在lca到u之间
    {
        int depk=dep[u]-k+1;///求第k个点的深度;
        int i;
        for(i=0;(1<<i)<dep[u];i++);
        for(int j=i-1;j>=0;j--)
        {
            if(dep[u]-(1<<j)>=depk)
                u=p[u][j];
        }
        return u;
    }
    else
    {
        int depk=dep[lca]+k-(dep[u]-dep[lca]+1);
        int i;
        for(i=0;(1<<i)<=dep[v];i++);
        for(int j=i-1;j>=0;j--)
        {
            if(dep[v]-(1<<j)>=depk)
                v=p[v][j];
        }
        return v;
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int m;
        int x,y,k;
        memset(dis,0,sizeof(dis));
        scanf("%d",&n);
        for(int i=0;i<=n;i++)
            g[i].clear();///之前将这个循环写成了for(int i=0;i<n;i++)   T了一万年......然后又改成用邻接表写...你好zz哦~~~
        for(int i=0;i<n-1;i++)
        {
            scanf("%d%d%d",&x,&y,&k);
            g[x].push_back(node(y,k));
            g[y].push_back(node(x,k));
        }
        init();
        char s[5];
        int a,b,c;
        while(scanf("%s",s))
        {
            if(s[1]=='O')
                break;
            else if(s[1]=='I')
            {
                scanf("%d%d",&a,&b);
                int ans=dis[a]+dis[b]-2*dis[LCA(a,b)];
                printf("%d\n",ans);
            }
            else if(s[0]=='K')
            {
                scanf("%d%d%d",&a,&b,&c);
                int ans=kkk(a,b,c);
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}

• 用邻接表

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
const int N=10010;
int p[N][15];///p[i][j]表示i的第2^j倍祖先;
int dep[N];///表示深度
int dis[N];///表示要求两点之间的距离
int head[N];
int n,l;
struct node
{
    int v,val,next;
}g[N*2];
///加边
void add(int u,int v,int val)
{
    g[l].v=v;
    g[l].val=val;
    g[l].next=head[u];
    head[u]=l;
    l++;
}
void dfs(int u,int f,int d)
{
    p[u][0]=f;
    dep[u]=d;
    for(int i=head[u];i!=-1;i=g[i].next)
    {
        int v=g[i].v;
        if(v==f)
            continue;
        dis[v]=dis[u]+g[i].val;
        dfs(v,u,d+1);
    }
}
void init()
{
    dfs(1,0,1);
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i<=n;i++)
            if(p[i][j]!=-1)
                p[i][j]=p[p[i][j-1]][j-1];
}
int LCA(int u,int v)
{
    if(dep[u]>dep[v])
        swap(u,v);
    int i;
    for(i=0;(1<<i)<=dep[v];i++);
    for(int j=i-1;j>=0;j--)
        if(dep[v]-(1<<j)>=dep[u])
            v=p[v][j];
    if(u==v)
        return u;
    for(int j=i-1;j>=0;j--)
    {
        if(p[u][j]!=p[v][j])
        {
            u=p[u][j];
            v=p[v][j];
        }
    }
    return p[u][0];
}
///求第k个节点
int kkk(int u,int v,int k)
{
    int lca=LCA(u,v);
    if(dep[u]-dep[lca]+1>=k)///说明第k个点在lca到u之间
    {
        int depk=dep[u]-k+1;///求第k个点的深度;
        int i;
        for(i=0;(1<<i)<=dep[u];i++);
        for(int j=i-1;j>=0;j--)
        {
            if(dep[u]-(1<<j)>=depk)
                u=p[u][j];
        }
        return u;
    }
    else
    {
        int depk=dep[lca]+k-(dep[u]-dep[lca]+1);
        int i;
        for(i=0;(1<<i)<=dep[v];i++);
        for(int j=i-1;j>=0;j--)
        {
            if(dep[v]-(1<<j)>=depk)
                v=p[v][j];
        }
        return v;
    }
}
int main()
{
    int t;
    int x,y,k;
    int a,b,c;
    char s[5];
    scanf("%d",&t);
    while(t--)
    {
        memset(dis,0,sizeof(dis));
        memset(head,-1,sizeof(head));
        memset(p,0,sizeof(p));
        memset(dep,0,sizeof(dep));
        l=0;
        scanf("%d",&n);
        for(int i=0;i<n-1;i++)
        {
            scanf("%d%d%d",&x,&y,&k);
            add(x,y,k);
            add(y,x,k);
        }
        init();
        while(scanf("%s",s))
        {
            if(s[1]=='O')
                break;
            else if(s[1]=='I')
            {
                scanf("%d%d",&a,&b);
                int ans=dis[a]+dis[b]-2*dis[LCA(a,b)];
                printf("%d\n",ans);
            }
            else if(s[0]=='K')
            {
                scanf("%d%d%d",&a,&b,&c);
                int ans=kkk(a,b,c);
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}