FZU oj Problem 2082 过路费

Problem 2082 过路费

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

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<vector>
  5 using namespace std;
  6 const int maxn = 50500;
  7 int son[maxn]; //表示该点重链的子节点
  8 int num[maxn]; //表示以该点为根的子树的节点数量
  9 int dep[maxn]; //表示该节点的深度
 10 int fa[maxn];  // 表示该节点的父亲节点
 11 int vis[maxn]; // 表示该节点在线段树中的编号
 12 int top[maxn]; // 表示这条重链的顶端节点
 13 int is[maxn];
 14 int edge[maxn][3];
 15 int now;
 16 struct Tree
 17 {
 18     int l;
 19     int r;
 20     int Sum;
 21 } tree[maxn*4];
 22 struct node
 23 {
 24     int to,val;
 25 } p;
 26 vector<node>E[maxn];
 27 void init()
 28 {
 29     now=0;
 30     memset(is,0,sizeof(is));
 31     memset(son,-1,sizeof(son));
 32     memset(tree,0,sizeof(tree));
 33     for(int i=0; i<maxn; i++)
 34         E[i].clear();
 35 }
 36 void dfs1(int u,int v,int step)    //第一遍dfs求出son，fa，num，dep
 37 {
 38     is[v]=1;
 39     dep[v]=step;
 40     num[v]=1;
 41     fa[v]=u;
 42     int len = E[v].size();
 43     for(int i=0; i<len; i++)
 44     {
 45         int to = E[v][i].to;
 46         if(!is[to])
 47         {
 48             dfs1(v,to,step+1);
 49             num[v]+=num[to];
 50             if(son[v]==-1||num[son[v]]<num[to])
 51             {
 52                 son[v]=to;
 53             }
 54         }
 55     }
 56     return ;
 57 }
 58 void dfs2(int u,int v)         // 第二遍dfs求出top和vis
 59 {
 60     is[v]=1;
 61     top[v]=u;
 62     vis[v]=now++;
 63     if(son[v]==-1)
 64         return ;
 65     else
 66         dfs2(u,son[v]);
 67     int len = E[v].size();
 68     for(int i=0; i<len; i++)
 69     {
 70         int to = E[v][i].to;
 71         if(!is[to])
 72         {
 73             if(to==fa[v]||to==son[v])
 74                 continue;
 75             dfs2(to,to);
 76         }
 77     }
 78 }
 79 void build(int v,int l,int r)
 80 {
 81     tree[v].l=l;
 82     tree[v].r=r;
 83     if( l == r )
 84     {
 85         tree[v].Sum=0;
 86         return;
 87     }
 88     int mid=( l+r )>>1;
 89     build( v<<1,l,mid );
 90     build( v<<1|1,mid+1,r );
 91     tree[v].Sum=0;
 92 }
 93 int query( int v,int l,int r)
 94 {
 95     if (l==tree[v].l&&r==tree[v].r)
 96         return tree[v].Sum;
 97     int mid=(tree[v].l+tree[v].r)>>1;
 98     if(l <= mid && r <= mid)
 99         return query(v<<1,l,r);
100     else if(l > mid)
101         return query(v<<1|1,l,r);
102     else
103         return query(v<<1,l,mid)+query(v<<1|1,mid+1,r);
104 }
105 void update(int v,int x,int m)
106 {
107     int l,r;
108     l = tree[v].l;
109     r = tree[v].r;
110     int mid = (l + r) / 2;
111     if(l == r)
112     {
113         tree[v].Sum = m;
114         return;
115     }
116     if(x <= mid)
117         update(v<<1,x,m);
118     else
119         update(v<<1|1,x,m);
120     tree[v].Sum=query(v<<1,l,mid)+query(v<<1|1,mid+1,r);
121 }
122 int main()
123 {
124     int n,m;
125     while(~scanf("%d%d",&n,&m))
126     {
127         init();
128         for(int i=1; i<=n-1; i++)
129         {
130             scanf("%d%d%d",&edge[i][0],&edge[i][1],&edge[i][2]);
131             p.to=edge[i][1],p.val=edge[i][2];
132             E[edge[i][0]].push_back(p);
133             p.to=edge[i][0],p.val=edge[i][2];
134             E[edge[i][1]].push_back(p);
135         }
136         dfs1(1,1,1);
137         memset(is,0,sizeof(is));
138         dfs2(1,1);
139         build(1,1,n);
140         for(int i = 1; i <= n-1; i++)
141         {
142             if(dep[edge[i][0]] < dep[edge[i][1]])
143                 swap(edge[i][0],edge[i][1]);
144             update(1,vis[edge[i][0]]+1,edge[i][2]);
145         }
146         while(m--)
147         {
148             int x,y,z,q,w;
149             scanf("%d%d%d",&x,&y,&z);
150             if(x)
151             {
152                 q = top[y],w = top[z];
153                 int ans = 0;
154                 while(q != w)     //不在一条重链上，就爬树
155                 {
156                     if(dep[q] < dep[w])
157                     {
158                         swap(q,w);
159                         swap(y,z);
160                     }
161                     ans += query(1,vis[q]+1,vis[y]+1);
162                     y = fa[q];
163                     q = top[y];
164                 }
165                 if(y != z)        //爬到一条重链上
166                 {
167                     if(dep[y] > dep[z])
168                         swap(y,z);
169                     ans += query(1,vis[son[y]]+1,vis[z]+1);
170                 }
171                 printf("%d\n",ans);
172             }
173             else
174             {
175                 update(1,vis[edge[y][0]]+1,z);
176             }
177         }
178 
179     }
180     return 0;
181 }