2370 小机房的树
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 钻石 Diamond
题目描述 Description
小机房有棵焕狗种的树，树上有N个节点，节点标号为0到N-1，有两只虫子名叫飘狗和大吉狗，分居在两个不同的节点上。有一天，他们想爬到一个节点上去搞基，但是作为两只虫子，他们不想花费太多精力。已知从某个节点爬到其父亲节点要花费 c 的能量（从父亲节点爬到此节点也相同），他们想找出一条花费精力最短的路，以使得搞基的时候精力旺盛，他们找到你要你设计一个程序来找到这条路，要求你告诉他们最少需要花费多少精力
输入描述 Input Description
第一行一个n，接下来n-1行每一行有三个整数u，v, c 。表示节点 u 爬到节点 v 需要花费 c 的精力。
第n+1行有一个整数m表示有m次询问。接下来m行每一行有两个整数 u ，v 表示两只虫子所在的节点
输出描述 Output Description
一共有m行，每一行一个整数，表示对于该次询问所得出的最短距离。
样例输入 Sample Input
3
1 0 1
2 0 1
3
1 0
2 0
1 2
样例输出 Sample Output
1
1
2
数据范围及提示 Data Size & Hint
1<=n<=50000， 1<=m<=75000， 0<=c<=1000
思路:
裸的求LCA的题
坑点:
记住输入的时候是从0开始编的号！！！
上代码:
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std; const int N = ;
const int M = ;
int top=,cnt=,dad[N],ans[N],dis[N],lca[M];
bool used[N]; struct heads {
int head;
}v1[N],v2[N]; struct edge {
int v,next,w;
}e1[N<<]; struct qedge {
int u,v,next;
}e2[M<<]; void chu()
{
memset(v1,-,sizeof(v1));
memset(v2,-,sizeof(v2));
memset(used,,sizeof(used));
} void add1(int u,int v,int w)
{
e1[++top].w=w;
e1[top].v=v;
e1[top].next=v1[u].head;
v1[u].head=top;
} void add2(int u,int v)
{
e2[++cnt].u=u;
e2[cnt].v=v;
e2[cnt].next=v2[u].head;
v2[u].head=cnt;
} int getdad(int x)
{return dad[x] = x == dad[x] ? x : getdad(dad[x]);} int getdis(int i)
{return dis[e2[i<<].u]+dis[e2[i<<].v]-(dis[lca[i]]<<);} void Tarjan(int u)
{
dad[u]=u;
used[u]=true;
for(int i=v1[u].head;i!=-;i=e1[i].next)
{
int v=e1[i].v;
if(used[v])
continue;
dis[v]=dis[u]+e1[i].w;
Tarjan(v);
dad[v]=u;
}
int Ms;
for(int i=v2[u].head;i!=-;i=e2[i].next)
{
int v = e2[i].u == u ? e2[i].v : e2[i].u;
if(used[v])
lca[i>>]=getdad(dad[v]);
}
} int main()
{
int n,m,u,v,w;
scanf("%d",&n);
chu();
--n;
while(n--)
{
scanf("%d%d%d",&u,&v,&w);
++u,++v;///从0开始编号的
add1(u,v,w),add1(v,u,w);
}
scanf("%d",&m);
for(int i=;i<=m;i++)
{
scanf("%d%d",&u,&v);
++u,++v;
add2(u,v),add2(v,u);
}
Tarjan();
for(int i=;i<=m;i++)
printf("%d\n",getdis(i));
return ;
}