How far away
【题目链接】How far away
【题目类型】dfs+邻接表
&题意：
题目大意：一个村子里有n个房子，这n个房子用n-1条路连接起来，接下了有m次询问，每次询问两个房子a,b之间的距离是多少。
&题解：
我以为是LCA的题,但dfs居然也能过,感觉是数据有点弱,(时间复杂度是4000x200x10,想了想10组又不能全是200,所以应该勉强可以)但学到了邻接表的数组形式,用数组表示链表,很厉害的样子,感觉和前向星好相似啊 
&代码：
#include <cstdio>
#include <bitset>
#include <iostream>
#include <set>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define fo(i,a,b) for(int i=(a);i<=(b);i++)
#define fd(i,a,b) for(int i=(a);i>=(b);i--)
const int maxn = 80000 + 7;
struct Edge {
int u, v, w, nx;
} G[maxn];
int id, ft[maxn], n, m, vis[maxn], ans, ok, vv, K;
void Add(int u, int v, int w) {
G[id].u = u, G[id].v = v, G[id].w = w;
G[id].nx = ft[u];
ft[u] = id++;
}
void dfs(int d, int num) {
if(ok) return;
if(d == vv) {
ans = num;
ok = 1; return ;
}
vis[d] = 1;
for(int i = ft[d]; ~i; i = G[i].nx) {
if(!vis[G[i].v]) {
dfs(G[i].v, num + G[i].w);
}
}
}
int main() {
freopen("E:1.in", "r", stdin);
int T; scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
int u, v, w;
id = 0;
memset(ft, -1, sizeof(ft));
fo(i, 2, n) {
scanf("%d%d%d", &u, &v, &w);
Add(u, v, w);
Add(v, u, w);
}
fo(i, 1, m) {
scanf("%d%d", &u, &vv);
memset(vis, 0, sizeof(vis));
ok = 0;
vis[u] = 1;
dfs(u, 0);
printf("%d
", ans);
}
}
return 0;
}