Timus Online Judge(Ural)1471 Distance in the Tree题解

Timus

题目简述：2/3/4/3/lca

传送门：1471. Distance in the Tree

题面

A weighted tree is given. You must find the distance between two given nodes.
Input

输入

The first line contains the number of nodes of the tree n (1 ≤ n ≤ 50000). The nodes are numbered from 0 to n – 1. Each of the next n – 1 lines contains three integers u, v, w, which correspond to an edge with weight w (0 ≤ w ≤ 1000) connecting nodes u and v. The next line contains the number of queries m (1 ≤ m ≤ 75000). In each of the next m lines there are two integers.

输出

For each query, output the distance between the nodes with the given numbers.

样例

input:
3
1 0 1
2 0 1
3
0 1
0 2
1 2
output:
1
1
2

分析

题意：给定一棵n（$1\leqslant n\leqslant 5\cdot 10^4$）个点的树，求m($1\leqslant m\leqslant 7.5\cdot 10^4$)次询问任意两点树上距离

可以一边dfs求树上每个点与根的距离，顺便做lca预处理，然后就很显然是lca裸题了

代码

#include<stdio.h>
const int maxn=1000005;
int i,j,k,m,n,s,e;
int start[maxn],to[maxn],then[maxn],worth[maxn],dis[maxn],dep[maxn],fore[maxn][40];
inline void add(int x,int y,int z){
    then[++e]=start[x],start[x]=e,to[e]=y,worth[e]=z;
}
void dfs(int x,int last){
    dep[x]=dep[last]+1,fore[x][0]=last;
    for(int i=1;i<=30;i++)
        fore[x][i]=fore[fore[x][i-1]][i-1];
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        dis[y]=dis[x]+worth[i];
        dfs(y,x);
    }
}
int lca(int a,int b){
    if(dep[a]<dep[b])
        a+=b,b=a-b,a-=b;
    for(int i=30;i>=0;i--)
        if(dep[fore[a][i]]>=dep[b])
            a=fore[a][i];
    if(a==b)
        return a;
    for(int i=30;i>=0;i--)
        if(fore[a][i]!=fore[b][i])
            a=fore[a][i],b=fore[b][i];
    return fore[a][0];
}
int main(){
    scanf("%d",&n);
    for(i=1;i<n;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z),add(y,x,z);
    }
    dfs(s,0);
    scanf("%d",&m);
    for(i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d",&a,&b);
        c=lca(a,b);
        printf("%d\n",dis[a]+dis[b]-dis[c]*2);
    }
    return 0;
}