Fzu Problem 2082 过路费 LCT,动态树

题目：http://acm.fzu.edu.cn/problem.php?pid=2082

Problem 2082 过路费

Accept: 528 Submit: 1654
Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

有n座城市，由n-1条路相连通，使得任意两座城市之间可达。每条路有过路费，要交过路费才能通过。每条路的过路费经常会更新，现问你，当前情况下，从城市a到城市b最少要花多少过路费。

Input

有多组样例，每组样例第一行输入两个正整数n,m(2 <= n<=50000，1<=m <= 50000),接下来n-1行，每行3个正整数a b c，(1 <= a,b <= n , a != b , 1 <= c <= 1000000000).数据保证给的路使得任意两座城市互相可达。接下来输入m行，表示m个操作，操作有两种：一. 0 a b，表示更新第a条路的过路费为b，1 <= a <= n-1 ；二. 1 a b ，表示询问a到b最少要花多少过路费。

Output

对于每个询问，输出一行，表示最少要花的过路费。

Sample Input

2 3 1 2 1 1 1 2 0 1 2 1 2 1

Sample Output

1 2

Source

FOJ有奖月赛-2012年4月（校赛热身赛）

Submit Back Status Discuss

题解：

直接动态树维护树上两点间的和即可。。。

注意开long long。。。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<cmath>
  5 #include<iostream>
  6 #include<algorithm>
  7 using namespace std;
  8 #define LL long long
  9 #define MAXN 50010
 10 struct node
 11 {
 12     int left,right,val;
 13     LL sum;
 14 }tree[MAXN*2];
 15 int father[MAXN*2],Stack[2*MAXN],rev[2*MAXN];
 16 int read()
 17 {
 18     int s=0,fh=1;char ch=getchar();
 19     while(ch<'0'||ch>'9'){if(fh=='-')fh=-1;ch=getchar();}
 20     while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
 21     return s*fh;
 22 }
 23 int isroot(int x)
 24 {
 25     return tree[father[x]].left!=x&&tree[father[x]].right!=x;
 26 }
 27 void pushdown(int x)
 28 {
 29     int l=tree[x].left,r=tree[x].right;
 30     if(rev[x]!=0)
 31     {
 32         rev[x]^=1;rev[l]^=1;rev[r]^=1;
 33         swap(tree[x].left,tree[x].right);
 34     }
 35 }
 36 void Pushup(int x)
 37 {
 38     int l=tree[x].left,r=tree[x].right;
 39     tree[x].sum=tree[l].sum+tree[r].sum+tree[x].val;
 40 }
 41 void rotate(int x)
 42 {
 43     int y=father[x],z=father[y];
 44     if(!isroot(y))
 45     {
 46         if(tree[z].left==y)tree[z].left=x;
 47         else tree[z].right=x;
 48     }
 49     if(tree[y].left==x)
 50     {
 51         father[x]=z;father[y]=x;tree[y].left=tree[x].right;tree[x].right=y;father[tree[y].left]=y;
 52     }
 53     else
 54     {
 55         father[x]=z;father[y]=x;tree[y].right=tree[x].left;tree[x].left=y;father[tree[y].right]=y;
 56     }
 57     Pushup(y);Pushup(x);
 58 }
 59 void splay(int x)
 60 {
 61     int top=0,i,y,z;Stack[++top]=x;
 62     for(i=x;!isroot(i);i=father[i])Stack[++top]=father[i];
 63     for(i=top;i>=1;i--)pushdown(Stack[i]);
 64     while(!isroot(x))
 65     {
 66         y=father[x];z=father[y];
 67         if(!isroot(y))
 68         {
 69             if((tree[y].left==x)^(tree[z].left==y))rotate(x);
 70             else rotate(y);
 71         }
 72         rotate(x);
 73     }
 74 }
 75 void access(int x)
 76 {
 77     int last=0;
 78     while(x!=0)
 79     {
 80         splay(x);
 81         tree[x].right=last;Pushup(x);
 82         last=x;x=father[x];
 83     }
 84 }
 85 void makeroot(int x)
 86 {
 87     access(x);splay(x);rev[x]^=1;
 88 }
 89 void link(int u,int v)
 90 {
 91     makeroot(u);father[u]=v;splay(u);
 92 }
 93 void cut(int u,int v)
 94 {
 95     makeroot(u);access(v);splay(v);father[u]=tree[v].left=0;
 96 }
 97 int findroot(int x)
 98 {
 99     access(x);splay(x);
100     while(tree[x].left!=0)x=tree[x].left;
101     return x;
102 }
103 int main()
104 {
105     int n,m,i,fh,aa,bb,cc;
106     while(scanf("%d %d",&n,&m)!=EOF)
107     {
108         for(i=0;i<=2*n;i++)tree[i].sum=tree[i].left=tree[i].right=tree[i].val=father[i]=rev[i]=0;
109         for(i=1;i<n;i++)
110         {
111             aa=read();bb=read();cc=read();
112             tree[n+i].val=cc;
113             link(aa,n+i);link(n+i,bb);
114         }
115         for(i=1;i<=m;i++)
116         {
117             fh=read();aa=read();bb=read();
118             if(fh==0)
119             {
120                 splay(n+aa);
121                 tree[n+aa].val=bb;
122             }
123             else
124             {
125                 makeroot(aa);access(bb);splay(bb);
126                 printf("%lld
",tree[bb].sum);
127             }
128         }
129     }
130     return 0; 
131 }

View Code