比赛 ZLXOI2015Day2 评测结果 AAAAAAAAAA
题目名称 ZLX的陨落 最终得分 100
用户昵称 ppfish 运行时间 0.562 s
代码语言 C++ 内存使用 12.14 MiB
提交时间 2015-10-30 20:20:50
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;

template<class T>inline void Read(T &x)
{
    int f = 1;
    char t = getchar();
    while (t < '0' || t > '9') {
        if (t == '-') f = -1;
        t = getchar();
    }
    x = 0;
    while (t >= '0' && t <= '9') {
        x = x * 10 + t - '0';
        t = getchar();
    }
    x *= f;
}

int outp[105], tp;

template<class T>inline void write(T x)
{
    if (x < 0) putchar('-'), x = -x;
    tp = 0;
    do {
        outp[++tp] = x % 10;
        x /= 10;
    } while (x);
    while (tp) putchar('0' + outp[tp]), tp --;
    putchar('\n');
}

const int maxn = 100005;
const int maxm = 200005;
const int logn = 18;

int n, m, q;
int fst[maxn], u[maxm], v[maxm], w[maxm], nxt[maxm], e_cn;

int f[maxn][logn + 1], dep[maxn];
long long dis[maxn];

inline void addedge(int x, int y, int z)
{
    e_cn ++;
    u[e_cn] = x, v[e_cn] = y, w[e_cn] = z;
    nxt[e_cn] = fst[x], fst[x] = e_cn;
}

void input()
{
    int x, y, z;
    Read(n), Read(m);
    for (register int i = 1; i < n; i++) {
        Read(x), Read(y), Read(z);
        addedge(x, y, z);
        addedge(y, x, z);
    }
    Read(q);
    memset(f, -1, sizeof(f));
}

void dfs(int cn, int pr)
{
    f[cn][0] = pr;
    for (register int i = fst[cn]; i; i = nxt[i]) {
        if (v[i] != pr) {
            dis[v[i]] = dis[cn] + w[i];
            dep[v[i]] = dep[cn] + 1;
            dfs(v[i], cn);
        }
    }
}

void prepare()
{
    dfs(1, -1);
    for (register int k = 1; (1 << k) <= n; k++) {
        for (register int i = 1; i <= n; i++) {
            if (f[i][k - 1] != -1) {
                f[i][k] = f[f[i][k - 1]][k - 1];
            }
        }
    }
}

int lca(int x, int y)
{
    if (dep[x] < dep[y]) swap(x, y);
    for (register int k = logn; k >= 0; k--) {
        if (f[x][k] != -1 && dep[f[x][k]] >= dep[y]) {
            x = f[x][k];
        }
    }
    if (x == y) return x;
    for (register int k = logn; k >= 0; k--) {
        if (f[x][k] != -1 && f[y][k] != -1 && f[x][k] != f[y][k]) {
            x = f[x][k];
            y = f[y][k];
        }
    }
    return f[x][0];
}

void solve()
{
    int x, y;
    while (q --) {
        Read(x), Read(y);
        write(dis[x] + dis[y] - 2 * dis[lca(x, y)]);
    }
}

int main()
{
    freopen("ThefallingofZLX.in", "r", stdin);
    freopen("ThefallingofZLX.out", "w", stdout);

    input();
    prepare();
    solve();
    
    fclose(stdin);
    fclose(stdout);
    return 0;
}