记录编号	297669	评测结果	AAAAAAAAAA
题目名称	[USACO Oct08] 牧场旅行	最终得分	100
用户昵称	Magic_Sheep	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-08-18 10:23:46	内存使用	0.00 MiB

#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int maxn=10010;
vector<int> f[maxn];
vector<int> g[maxn];
int x,y,z;
int fa[maxn],dep[maxn],son[maxn],sz[maxn],top[maxn],dist[maxn];
void dfs1(int u,int fath,int deep,int dis)
{
    dep[u]=deep;fa[u]=fath;dist[u]=dis;
    sz[u]=1;son[u]=0;
    for(int i=0;i<f[u].size();i++)
    {
        int v=f[u][i];
        //cout<<v<<endl;
        if(v==fath) continue;
        dfs1(v,u,deep+1,dist[u]+g[u][i]);
        sz[u]+=sz[v];
        if(sz[son[u]]<sz[v])
        son[u]=v;
    }
    return;
}
void dfs2(int u,int tp)
{
    top[u]=tp;
    if(son[u]) dfs2(son[u],tp);
    for(int i=0;i<f[u].size();i++)
    {
        int v=f[u][i];
        //cout<<v<<endl;
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
int lca(int x,int y)
{
    int tx=top[x],ty=top[y];
    while(tx!=ty)
    {
        if(dep[tx]<dep[ty]) y=fa[ty],ty=top[y];
        else x=fa[tx],tx=top[x];
    }
    return dep[x]<dep[y] ? x: y;
}
int MAIN()
{
    freopen("pwalk.in","r",stdin);
    freopen("pwalk.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        f[x].push_back(y);
        f[y].push_back(x);
        g[x].push_back(z);
        g[y].push_back(z);
    }
    dfs1(1,-1,0,0);
    dfs2(1,1);
    //for(int i=1;i<n;i++) cout<<son[i]<<endl;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",dist[x]+dist[y]-2*dist[lca(x,y)]);
    }
    return 0;
}
int main(){;}
int EZOI=MAIN();
/*
6 5
1 2 2
2 3 2
2 4 2
1 5 2
5 6 2
3 6
3 4
2 5
2 6
3 5
*/