记录编号	437220	评测结果	AAAAAAAAAA
题目名称	[USACO Oct08] 牧场旅行	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2017-08-13 20:17:07	内存使用	0.60 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

inline char getc(void) { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int read(void) { 
    register int res = 0;
    register char tmp = getc();
    while(!isdigit(tmp)) tmp = getc();
    while(isdigit(tmp))
        res = ((res + (res << 2)) << 1) + (tmp ^ 0x30),
        tmp = getc();
    return res;
}

#define MAXN (1010)

struct EDGE{ 
    int to, val;
    EDGE *ne;
    EDGE(int t, EDGE *n, int v) { 
        to = t, ne = n, val = v;
    }
};

struct NODE{ 
    int sum;
    NODE *ls, *rs;
    NODE() { 
        ls = rs = NULL;
    }
};

NODE *Build(int l, int r);
inline void add_edge(int fr, int to, int val);
void dfs1(int u);
int Query(NODE *node, int l, int r, int L, int R);
void dfs2(int u, int tp);
inline int LCA(int a, int b);

int val[MAXN], N, Q;
int top[MAXN], siz[MAXN], fat[MAXN], fa[MAXN];
int dfn[MAXN], id[MAXN], dep[MAXN];
EDGE *head[MAXN];
NODE *root;

int main() { 
#ifndef LOCAL
    freopen("pwalk.in", "r", stdin);
    freopen("pwalk.out", "w", stdout);
#endif
    N = read(), Q = read();
    for(int i = 1, fr, to; i < N; ++i) { 
        fr = read(), to = read();
        add_edge(fr, to, read());
    }
    fa[1] = dep[1] = 1;
    dfs1(1);
    dfs2(1, 1);
    root = Build(1, N);
    for(int i = 0; i < Q; ++i) { 
        printf("%d\n", LCA(read(), read()));
    }
}

inline void add_edge(int fr, int to, int val) { 
    head[fr] = new EDGE(to, head[fr], val);
    head[to] = new EDGE(fr, head[to], val);
    return ;
}

void dfs1(int u) { 
    siz[u] = 1;
    for(register EDGE *e = head[u]; e; e = e->ne) { 
        if(e->to == fa[u]) continue;
        val[e->to] = e->val;
        fa[e->to] = u;
        dep[e->to] = dep[u] + 1;
        dfs1(e->to);
        siz[u] += siz[e->to];
        if(siz[fat[u]] < siz[e->to]) fat[u] = e->to;
    }
    return ;
}

NODE *Build(int l, int r) { 
    NODE *p = new NODE();
    if(l ^ r) { 
        int mid = (l + r) >> 1;
        p->ls = Build(l, mid);
        p->rs = Build(mid + 1, r);
        p->sum = p->ls->sum + p->rs->sum;
    } else p->sum = val[id[l]];
    return p;
}

int Query(NODE *node, int l, int r, int L, int R) { 
    if(l == L && r == R) return node->sum;
    int mid = (L + R) >> 1;
    if(r <= mid) return Query(node->ls, l, r, L, mid);
    if(mid < l) return Query(node->rs, l, r, mid + 1, R);
    return Query(node->ls, l, mid, L, mid) + Query(node->rs, mid + 1, r, mid + 1, R);
}

void dfs2(int u, int tp) { 
    static int cnt = 0;
    top[u] = tp;
    id[dfn[u] = ++cnt] = u;
    if(!fat[u]) return ;
    dfs2(fat[u], tp);
    for(register EDGE *e = head[u]; e; e = e->ne) { 
        if(dfn[e->to]) continue;
        dfs2(e->to, e->to);
    }
    return ;
}

inline int LCA(int a, int b) { 
    register int res = 0;
    while(top[a] ^ top[b]) { 
        if(dep[top[a]] < dep[top[b]]) a ^= b ^= a ^= b;
        res += Query(root, dfn[top[a]], dfn[a], 1, N);
        a = fa[top[a]];
    }
    if(dep[a] > dep[b]) a ^= b ^= a ^= b;
    res += Query(root, dfn[a], dfn[b], 1, N);
    return res - val[a];
}