记录编号	309496	评测结果	AAAAAAAAAA
题目名称	距离	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.149 s
提交时间	2016-09-19 20:43:53	内存使用	0.61 MiB

#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <algorithm>
#include <queue>
#include <list>
#include <vector>
#include <cctype>
using namespace std;
#define BETTER_CODE __attribute__((optimize("O3")))

BETTER_CODE
int fast_read()
{
    int r;
    char c;
    while(c = getchar())    
    {
        if(c >= '0' && c <= '9')
        {
            r = c^0x30;
            break;
        }
    }
    while(isdigit(c = getchar()))
        r = (r<<3)+(r<<1)+(c^0x30);
    return r;
}
#define MAXN 10003
vector<pair<int, int> > G[MAXN];
struct edge
{
    int from, to, value;
    void scan()
    {
        from = fast_read();
        to = fast_read();
        value = fast_read();
        G[from].push_back(make_pair(to, value));
        G[to].push_back(make_pair(from, value));
    }
}edges[MAXN];
int dist[MAXN];
int top[MAXN], son[MAXN], parent[MAXN], deep[MAXN], size[MAXN];
BETTER_CODE
void dfs(int u, int f, int d)
{
    deep[u] = d;
    parent[u] = f;
    size[u] = 1;
    for(int i = 0; i < G[u].size(); i++)
    {
        int to = G[u][i].first;
        int cst = G[u][i].second;
        if(to != f)
        {
            dist[to] = dist[u] + cst;
            dfs(to, u, d+1);
            size[u] += size[to];
            if(size[to] > size[son[u]])
                son[u] = to;
        }
            
    }
}
BETTER_CODE
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].first;
        if(to != parent[u] && to != son[u])
            dfs(to, to);
    }
}
BETTER_CODE
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;
}
BETTER_CODE
int main()
{
    freopen("distance.in", "r", stdin);
    freopen("distance.out", "w", stdout);
    int n, m;
    n = fast_read();
    m = fast_read();
    for(int i = 1; i < n; i++)
        edges[i].scan();
    dfs(1, 0, 1);
    dfs(1, 1);
    for(int i = 0; i < m; i++)
    {
        int a, b;
        a = fast_read();
        b = fast_read();
        printf("%d\n", dist[a]+dist[b]-2*dist[lca(a,b)]);
    }
    return 0;
}