Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 18652 Accepted Submission(s):
7268
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
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
Recommend
带权的LCA问题
我们用g[i]表示i号节点走到根的权值
那么两个点之间的路径权值为,$g[x]+g[y]-2*g[LCA(x,y)]$
大概是这个样子
被圆圈出来的是需要减去的
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1e5+;
inline int read()
{
char c=getchar();int x=,f=;
while(c<''||c>'') {if(c=='-') f=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-,c=getchar();return x*f;
}
int n,m,S=;
int f[MAXN][],deep[MAXN],g[MAXN];
struct node
{
int u,v,w,nxt;
}edge[MAXN];
int head[MAXN];
int num=;
inline void add_edge(int x,int y,int z)
{
edge[num].u=x;
edge[num].v=y;
edge[num].w=z;
edge[num].nxt=head[x];
head[x]=num++;
}
void dfs(int now)
{
for(int i=head[now];i!=-;i=edge[i].nxt)
if(deep[edge[i].v]==)
{
deep[edge[i].v]=deep[now]+;
f[edge[i].v][]=now;
g[edge[i].v]=g[now]+edge[i].w;
dfs(edge[i].v);
} }
inline void pre()
{
for(int i=;i<=;i++)
for(int j=;j<=n;j++)
f[j][i]=f[f[j][i-]][i-];
}
inline int LCA(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y);
for(int i=;i>=;i--)
if(deep[f[x][i]]>=deep[y])
x=f[x][i];
if(x==y) return x; for(int i=;i>=;i--)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][];
}
int main()
{
int T=read();
while(T--)
{
n=read();m=read();
memset(head,-,sizeof(head));num=;
memset(f,,sizeof(f));
memset(deep,,sizeof(deep));
for(int i=;i<=n-;i++)
{
int x=read(),y=read(),z=read();
add_edge(x,y,z);
add_edge(y,x,z);
}
deep[S]=;
dfs(S);pre();
while(m--)
{
int x=read(),y=read();
printf("%d\n",g[x]+g[y]-*g[LCA(x,y)]);
}
} return ;
}