记录编号	340956	评测结果	AAAAAAAAAA
题目名称	[USACO Oct08] 牧场旅行	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.034 s
提交时间	2016-11-07 09:15:10	内存使用	0.22 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdarg>
#include <algorithm>
#include <vector>
#include <list>
#include <queue>
#include <functional>
using namespace std;
#define MAXN 1001
vector<int> G[MAXN];
vector<int> D[MAXN];
int size[MAXN], top[MAXN], parent[MAXN];
int deep[MAXN], son[MAXN];
int dist[MAXN];
void dfs(int u, int f, int d)
{
    size[u] = 1;
    parent[u] = f;
    deep[u] = d;
    for(int i = 0; i < G[u].size(); i++)
    {
        int to = G[u][i];
        if(to != f)
        {
            dist[to] = dist[u] + D[u][i];
            dfs(to, u, d+1);
            size[u] += size[to];
            if(size[son[u]] < size[to])
                son[u] = to;
        }
    }
}
void dfs(int u, int tp)
{
    top[u] = tp;
    if(!son[u])return;
    dfs(son[u], tp);
    for(int i = 0; i < G[u].size(); i++)
    {
        int to = G[u][i];
        if(to != parent[u] && to != son[u])
            dfs(to, to);
    }
}
int lca(int u, int v)
{
    int t1 = top[u], t2 = top[v];
    while(t1 != t2)
    {
        if(deep[t1] < deep[t2])
        {
            swap(u, v);
            swap(t1, t2);
        }
        u = parent[t1];
        t1 = top[u];
    }
    return deep[u]<deep[v]?u:v;
}
inline int getdist(int u, int v)
{
    return dist[u]+dist[v]-(dist[lca(u, v)]<<1);
}
vector<int> Z[MAXN];
int main()
{
    char *__p__ = (char *)malloc(64<<20)+(64<<20);
    __asm__("movl %0, %%esp\n" :: "r"(__p__));
    freopen("pwalk.in", "r", stdin);
    freopen("pwalk.out", "w", stdout);
    int n, q;
    scanf("%d %d", &n, &q);
    for(int i = 1; i < n; i++)
    {
        int a, b, l;
        scanf("%d %d %d", &a, &b, &l);
        G[a].push_back(b);
        G[b].push_back(a);
        D[a].push_back(l);
        D[b].push_back(l);
    }
    for(int i = 1; i <= n; i++)
        if(!size[i])
        {
            dfs(i, 0, 0);
            dfs(i, i);
        }
    while(q--)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", getdist(a, b));
    }
    return 0;
}