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

#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;

const int maxn=1000+10;
const int log_maxn=20;

struct thing {
       int dis;
       int point;
};

vector<thing> G[maxn];
int root,n,q;
int deep[maxn],parent[log_maxn][maxn],dis[maxn];

int dfs(int v,int p,int d,int diss)
{
    parent[0][v]=p;
    deep[v]=d;
    dis[v]=diss;
    for(int i=0;i<G[v].size();i++)
    {
            //deep[parent[0][v]]+=G[v][i].dis;
            if(G[v][i].point!=p) dfs(G[v][i].point,v,d+1,diss+G[v][i].dis);
    }
}

int init(int V)
{
    dfs(root,-1,0,0);
    for(int k=0;k+1<log_maxn;k++)
    {
            for(int v=1;v<=V;v++)
            {
                    if(parent[k][v]<0) parent[k+1][v]=-1;
                    else parent[k+1][v]=parent[k][parent[k][v]];
            }
    }
}

int lca(int u,int v)
{
    if(deep[u]>deep[v]) swap(u,v);
    for(int k=0;k<log_maxn;k++)
    {
            if(deep[v]-deep[u]>>k&1)
            {
                  v=parent[k][v];
            }
    }
    if(u==v) return u;
    for(int k=log_maxn-1;k>=0;k--)
    {
    	if(parent[k][u]!=parent[k][v])
    	{
		    u=parent[k][u];
            v=parent[k][v];
		}
    }
    return parent[0][u];
}

int MAIN()
{
    freopen("pwalk.in","r",stdin);
    freopen("pwalk.out","w",stdout);
    int x,y,z;
    cin>>n>>q;
    for(int i=1;i<n;i++)
    {
            cin>>x>>y>>z;
            G[x].push_back((thing){z,y});
            G[y].push_back((thing){z,x});
    }
    root=n/2;
    init(n);
    for(int i=1;i<=q;i++)
    {
            cin>>x>>y;
            int t=dis[lca(x,y)];
            cout<<dis[x]+dis[y]-t*2<<endl;
    }
    return 0;
}

int main() {;}

int EZOI=MAIN();