Description
N头牛（2<=n<=1000）别人被标记为1到n，在同样被标记1到n的n块土地上吃草，第i头牛在第i块牧场吃草。 这n块土地被n-1条边连接。 奶牛可以在边上行走，第i条边连接第Ai，Bi块牧场，第i条边的长度是Li（1<=Li<=10000）。 这些边被安排成任意两头奶牛都可以通过这些边到达的情况，所以说这是一棵树。 这些奶牛是非常喜欢交际的，经常会去互相访问,他们想让你去帮助他们计算Q(1<=q<=1000)对奶牛之间的距离。
Input
*第一行：两个被空格隔开的整数：N和Q
*第二行到第n行：第i+1行有两个被空格隔开的整数：AI，BI，LI
*第n+1行到n+Q行：每一行有两个空格隔开的整数：P1，P2，表示两头奶牛的编号。
Output
*第1行到第Q行：每行输出一个数，表示那两头奶牛之间的距离。
Sample Input
4 2 2 1 2 4 3 2 1 4 3 1 2 3 2
Sample Output
2 7
HINT
Source
Solution
裸LCA，看不懂代码的人都是
1 #include2 using namespace std; 3 struct edge 4 { 5 int v, w, nxt; 6 }e[2005]; 7 struct query 8 { 9 int u, v, nxt;10 }q[2005];11 int efst[1005], qfst[1005], fa[1005], lca[1005], dis[1005];12 bool vis[1005];13 14 void addedge(int i, int u, int v, int w)15 {16 e[i] = (edge){v, w, efst[u]}, efst[u] = i;17 }18 19 void addquery(int i, int u, int v)20 {21 q[i] = (query){u, v, qfst[u]}, qfst[u] = i;22 }23 24 int get_dis(int i)25 {26 return dis[q[i << 1].u] + dis[q[i << 1].v] - 2 * dis[lca[i]];27 }28 29 int getfa(int x)30 {31 return fa[x] = x == fa[x] ? x : getfa(fa[x]);32 }33 34 void Tarjan(int u)35 {36 fa[u] = u, vis[u] = true;37 for(int i = efst[u]; i; i = e[i].nxt)38 if(!vis[e[i].v])39 {40 dis[e[i].v] = dis[u] + e[i].w;41 Tarjan(e[i].v);42 fa[e[i].v] = u;43 }44 for(int i = qfst[u]; i; i = q[i].nxt)45 {46 int v = q[i].u == u ? q[i].v : q[i].u;47 if(vis[v]) lca[i >> 1] = getfa(fa[v]);48 }49 }50 51 int main()52 {53 int n, q, u, v, w;54 cin >> n >> q;55 for(int i = 1; i < n; i++)56 {57 cin >> u >> v >> w;58 addedge(i << 1, u, v, w);59 addedge(i << 1 | 1, v, u, w);60 }61 for(int i = 1; i <= q; i++)62 {63 cin >> u >> v;64 addquery(i << 1, u, v);65 addquery(i << 1 | 1, v, u);66 }67 Tarjan(1);68 for(int i = 1; i <= q; i++)69 cout << get_dis(i) << endl;70 return 0;71 }