付代码
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<iostream>
using namespace std;
int maxx(int a,int b){return a>b?a:b;}
int minn(int a,int b){return a<b?a:b;}
void swap(int &a,int &b){a^=b; b^=a; a^=b; return;}
#define maxn 41000
struct node{int lc,rc,sum,d,fa;
            #define lc(x) tr[x].lc
            #define rc(x) tr[x].rc
            #define sum(x) tr[x].sum
            #define fa(x) tr[x].fa
            #define d(x) tr[x].d
            }tr[maxn];
struct edge_node{int x,y,d,next;}edge[maxn*2];
int n,m,first[maxn],len,list[maxn],head,tail;
bool bo[maxn];
inline bool isroot(int x){return lc(fa(x))!=x && rc(fa(x))!=x;}
inline void updata(int x){sum(x)=sum(lc(x))+sum(rc(x))+d(x);return;}
inline void ins(int x,int y,int z){
    len++;
    edge[len].x=x; edge[len].y=y; edge[len].d=z;
    edge[len].next=first[x]; first[x]=len;
    return;
}
inline void bfs(){
    int x,y,k;
    head=1; tail=2; list[1]=1; bo[1]=true; fa(1)=lc(1)=rc(1)=0;
    while (head!=tail){
        x=list[head];
        k=first[x];
        while (k!=-1){
            y=edge[k].y;
            if (!bo[y]){
                fa(y)=x; d(y)=edge[k].d; lc(y)=rc(y)=0; bo[y]=true;
                list[tail++]=y; if (tail>=10000) tail=1;
            }
            k=edge[k].next;
        }
        head++; if (head>=10000) head=1;
    }
    return;
}
inline void l_rotate(int x){
    int y,z; y=fa(x); z=fa(y);
    if (lc(z)==y) lc(z)=x;
    else if (rc(z)==y) rc(z)=x;
    fa(x)=z; fa(lc(x))=y; rc(y)=lc(x); lc(x)=y; fa(y)=x;
    updata(y);
    return;
}
inline void r_rotate(int x){
    int y,z; y=fa(x); z=fa(y);
    if (lc(z)==y) lc(z)=x;
    else if (rc(z)==y) rc(z)=x;
    fa(x)=z; fa(rc(x))=y; lc(y)=rc(x); rc(x)=y; fa(y)=x;
    updata(y);
    return;
}
inline void splay(int x){
    int y,z;
    while (!isroot(x)){
        y=fa(x); z=fa(y);
        if (isroot(y)){
            if (lc(y)==x) r_rotate(x);
            else l_rotate(x);
        }else{
            if (lc(z)==y){
                if (lc(y)==x) r_rotate(y),r_rotate(x);
                else l_rotate(x),r_rotate(x);
            }else{
                if (lc(y)==x) r_rotate(x),l_rotate(x);
                else l_rotate(y),l_rotate(x);
            }
        }
    }
    updata(x);
    return;
}
inline void expose(int x){
    int y=0;
    while (x>0){
        splay(x);
        rc(x)=y; updata(x); y=x; x=fa(x);
    }
    return;
}
inline int qsum(int x,int y){
    expose(y);
    y=0;
    while (x>0){
        splay(x);
        if (!fa(x)) return sum(y)+sum(rc(x));
        rc(x)=y; updata(x); y=x; x=fa(x);
    }
    return -100000000;
}
int main(){
    int t,i,j,x,y,z;
    while (scanf("%d%d",&n,&m)!=EOF){
        memset(first+1,255,n*sizeof(int)); memset(bo+1,false,n*sizeof(bool)); len=0;
        for (i=1; i<=m; i++){
            scanf("%d%d%d",&x,&y,&z); getchar(); getchar();
            ins(x,y,z); ins(y,x,z);
        }
        bfs();
        scanf("%d",&t);
        while (t--){
            scanf("%d%d",&x,&y);
            printf("%d\n",qsum(x,y));
        }
    }
    return 0;
}

• 还请大家帮帮忙啊！！我初学动态树 (8) shuaige123 2012-06-13 12:49:08
  • http://ace.delos.com/FEB04_7.htm (14) rayafjyblue 2012-08-15 20:02:38
    • Re:http://ace.delos.com/FEB04_7.htm (16) 200907124 2013-07-26 11:50:19
    • 非常感谢楼主的数据！发现了很多细节上的问题 (45) lpl1998 2014-08-12 08:46:18
    • Re:http://ace.delos.com/FEB04_7.htm (16) lzliuyuwei 2016-09-24 10:09:32
    • Re:http://ace.delos.com/FEB04_7.htm (24) 2014sunrui 2017-11-01 15:53:25