http://acm.hdu.edu.cn/showproblem.php?pid=2586
How far away ？
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13821 Accepted Submission(s):
5195
Problem Description
There are n houses in the village and some
bidirectional roads connecting them. Every day peole always like to ask like
this "How far is it if I want to go from house A to house B"? Usually it hard to
answer. But luckily int this village the answer is always unique, since the
roads are built in the way that there is a unique simple path("simple" means you
can't visit a place twice) between every two houses. Yout task is to answer all
these curious people.
bidirectional roads connecting them. Every day peole always like to ask like
this "How far is it if I want to go from house A to house B"? Usually it hard to
answer. But luckily int this village the answer is always unique, since the
roads are built in the way that there is a unique simple path("simple" means you
can't visit a place twice) between every two houses. Yout task is to answer all
these curious people.
Input
First line is a single integer T(T<=10), indicating
the number of test cases.
For each test case,in the first line there are
two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses
and the number of queries. The following n-1 lines each consisting three numbers
i,j,k, separated bu a single space, meaning that there is a road connecting
house i and house j,with length k(0<k<=40000).The houses are labeled from
1 to n.
Next m lines each has distinct integers i and j, you areato answer
the distance between house i and house j.
the number of test cases.
For each test case,in the first line there are
two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses
and the number of queries. The following n-1 lines each consisting three numbers
i,j,k, separated bu a single space, meaning that there is a road connecting
house i and house j,with length k(0<k<=40000).The houses are labeled from
1 to n.
Next m lines each has distinct integers i and j, you areato answer
the distance between house i and house j.
Output
For each test case,output m lines. Each line represents
the answer of the query. Output a bland line after each test case.
the answer of the query. Output a bland line after each test case.
Sample Input
2
3 2
1 2 10
3 1 15
1 2
2 3
2 2
1 2 100
1 2
2 1
Sample Output
10
25
100
100
25
100
100
Source
题目大意：有T组数据 每组给出n个点由n-1条路连接，给出m次询问，求a和b两个村庄的距离
我实在不想吐槽，多组数据不用初始化也能A？中间把最近公共祖先输出了也能A！？逗我玩呢。
带领小学妹谢JustPenz233
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
vector<int> v[];
vector<int> w[];
int f[][];//f[i][j]表示i点向上2^j层的祖先
int g[][];//g[i][j]表示i点到从i向上2^j层的祖先的距离
int dep[];
int n,m;
void dfs(int pos,int pre,int depth)
{
dep[pos]=depth;
for(int i=;i<v[pos].size();i++)
{
int t=v[pos][i];
if(t==pre) continue;
f[t][]=pos;
g[t][]=w[pos][i];
dfs(t,pos,depth+);
}
}
int query(int a,int b)
{
int sum=;
if(dep[a]<dep[b]) swap(a,b);//深度较深的点
for(int i=;i>=;i--)//找到a在深度dep[b]处的祖先
{
if(dep[f[a][i]]>=dep[b])
{
sum+=g[a][i];//a到该祖先的距离
a=f[a][i];
}
}
if(a==b) return sum;//挪到相同深度后如果在同一点直接return
int x;
for(int i=;i>=;i--)//否则a和b一起往上蹦跶
{
if(f[a][i]!=f[b][i])
{
sum+=g[a][i];
a=f[a][i];
sum+=g[b][i];
b=f[b][i];
}
}
return sum+g[a][]+g[b][];//最后蹦跶到最近公共祖先的下一层，所以要再加上上一层
}
int main()
{
int T;
cin>>T;
while(T--)
{
scanf("%d%d",&n,&m);
memset(dep,-,sizeof dep);//多组数据我们初始化
memset(f,,sizeof f);
memset(g,,sizeof g);
for(int i=;i<n;i++)//md
v[i].clear(),w[i].clear();
for(int i=;i<n;i++)
{
int x,y,c;
cin>>x>>y>>c;
v[x].push_back(y);
w[x].push_back(c);
v[y].push_back(x);
w[y].push_back(c);
}
int xxx=v[].size();
dfs(,,);//dfs处理出每个点的深度，以及各种... for(int i=;<<i<=n;i++)
for(int j=;j<=n;j++)
f[j][i]=f[f[j][i-]][i-],
g[j][i]=g[f[j][i-]][i-]+g[j][i-];
for(int i=;i<=m;i++)
{
int x,y;
cin>>x>>y;
if(x==y) cout<<""<<endl;
else cout<<query(x,y)<<endl;
}
}
return ;
}