codevs 2370 小机房的树

题目描述 Description

小机房有棵焕狗种的树，树上有N个节点，节点标号为0到N-1，有两只虫子名叫飘狗和大吉狗，分居在两个不同的节点上。有一天，他们想爬到一个节点上去搞基，但是作为两只虫子，他们不想花费太多精力。已知从某个节点爬到其父亲节点要花费 c 的能量（从父亲节点爬到此节点也相同），他们想找出一条花费精力最短的路，以使得搞基的时候精力旺盛，他们找到你要你设计一个程序来找到这条路，要求你告诉他们最少需要花费多少精力

输入描述 Input Description

第一行一个n，接下来n-1行每一行有三个整数u，v, c 。表示节点 u 爬到节点 v 需要花费 c 的精力。
第n+1行有一个整数m表示有m次询问。接下来m行每一行有两个整数 u ，v 表示两只虫子所在的节点

输出描述 Output Description

一共有m行，每一行一个整数，表示对于该次询问所得出的最短距离。

样例输入 Sample Input

1 0 1

2 0 1

1 0

2 0

1 2

样例输出 Sample Output

数据范围及提示 Data Size & Hint

1<=n<=50000， 1<=m<=75000， 0<=c<=1000

思路：树链剖分求LCA模板题

#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int M = 50005;
int n, m, tot;
int to[M*2], net[M*2], head[M], cap[M*2];
int deep[M], top[M], dad[M], size[M], length[M];

void add(int u, int v, int w) {
    to[++tot] = v; net[tot] = head[u]; head[u] = tot; cap[tot] = w;
    to[++tot] = u; net[tot] = head[v]; head[v] = tot; cap[tot] = w;
}

void dfs(int now) {
    size[now] = 1;
    deep[now] = deep[dad[now]] + 1;
    for (int i = head[now]; i; i = net[i])
        if (to[i] != dad[now]) {
            dad[to[i]] = now;
            length[to[i]] = length[now] + cap[i];
            dfs(to[i]);
            size[now] += size[to[i]];
        }
}

void dfsl(int now) {
    int t = 0;
    if (!top[now]) top[now] = now;
    for (int i = head[now]; i; i = net[i])
        if (to[i] != dad[now] && size[to[i]] > size[t])
            t = to[i];
    if (t) {
        top[t] = top[now];
        dfsl(t);
    }
    for (int i = head[now]; i; i = net[i])
        if (to[i] != dad[now] && to[i] != t)
            dfsl(to[i]);
}

int lca(int x, int y) {
    while (top[x] != top[y]) {
        if (deep[top[x]] < deep[top[y]])
            swap(x, y);
        x = dad[top[x]];
    }
    return deep[x] > deep[y] ? y : x;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
    }
    dfs(0); dfsl(0);
    scanf("%d", &m);
    for (int i = 1; i <= m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        int t = lca(u, v);
        printf("%d
", length[u] + length[v] - length[t] * 2);
    }
    return 0;
}