CODEvs 2370 小机房的树 清流解法之树链剖分

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

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define N 500005
using namespace std;
int n,m,s,tot,dcnt;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
  if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct EDGE{
    int to,nex,v;
}ed[N*2];
struct tree{
    int son,fa,top,sz,s,e,dep,dis;
}tr[N];
int head[N*2],mp[N];
inline void add(int x,int y,int z){
    ++tot;
    ed[tot].nex=head[x];
    head[x]=tot;
    ed[tot].to=y;
    ed[tot].v=z;
}
void dfs1(int u,int d){
  //第二个参数是他到根的距离 
    tr[u].sz=1;
    tr[u].dis=d;
    for(int i=head[u];i;i=ed[i].nex)
       if(ed[i].to!=tr[u].fa){
           int hxr=ed[i].to;
           tr[hxr].dep=tr[u].dep+1;
           tr[hxr].fa=u;
           dfs1(hxr,d+ed[i].v);
           tr[u].sz+=tr[hxr].sz;
           if(tr[hxr].sz>tr[tr[u].son].sz)
             tr[u].son=hxr; 
       }
}
void dfs2(int u,int top){
    tr[u].top=top;
    tr[u].s=++dcnt;
    mp[dcnt]=u;
    if(tr[u].son){
        dfs2(tr[u].son,top);
        for(int i=head[u];i;i=ed[i].nex)
          if(ed[i].to!=tr[u].fa&&ed[i].to!=tr[u].son)
        dfs2(ed[i].to,ed[i].to);
    }
    tr[u].e=dcnt;
}
inline int find(int x,int y){
    int f1=tr[x].top;
    int f2=tr[y].top;
    while(f1!=f2){
        if(tr[f1].dep<tr[f2].dep){
            swap(f1,f2);
            swap(x,y);
        }
        x=tr[f1].fa;
        f1=tr[x].top;
    }
    if(tr[x].dep<tr[y].dep) return x;
    else return y;
}
int main(){
    n=read();
    for(register int i=1;i<n;i++){
        int u,v,c;
        u=read()+1;
        v=read()+1;
        c=read();
        add(u,v,c);
        add(v,u,c);
    }
    m=read();
    tr[1].dep=1;
    tr[1].dis=0;
    dfs1(1,0);
    dfs2(1,1);
    for(int i=1;i<=m;i++){
        int u,v;
        u=read()+1;
        v=read()+1;
        int gen=find(u,v);
        int ans=0;
        ans+=tr[u].dis;
        ans+=tr[v].dis;
        ans-=tr[gen].dis*2;
        printf("%d\n",ans);

    }
    return 0;
}
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务