FZU 2082（过路费）

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cmath>

 #include <algorithm>

 #include <cstring>

 #include <stack>

 #include <cctype>

 #include <queue>

 #include <string>

 #include <vector>

 #include <set>

 #include <map>

 #include <climits>

 #define lson rt<<1,l,mid

 #define rson rt<<1|1,mid+1,r

 #define fi first

 #define se second

 #define ping(x,y) ((x-y)*(x-y))

 #define mst(x,y) memset(x,y,sizeof(x))

 #define mcp(x,y) memcpy(x,y,sizeof(y))

 using namespace std;

 #define gamma 0.5772156649015328606065120

 #define MOD 1000000007

 #define inf 0x3f3f3f3f

 #define N 50005

 #define maxn 30010

 typedef pair<int,int> PII;

 typedef long long LL;

 LL read(){

     LL x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 int head[N],hcnt;

 int n,m,flag,L,R;

 int son[N],siz[N],fa[N],top[N];

 int id[N],tid,dep[N],posi[N];

 LL seg[N<<];

 struct Node{int to,nxt;LL v;}node[N<<];

 struct Edge{int x,y;LL v;}edge[N];

 void dfs1(int u,int f,int deep){

     fa[u]=f,dep[u]=deep,siz[u]=;

     for(int i=head[u];~i;i=node[i].nxt){

         int e=node[i].to;if(e==f)continue;

         dfs1(e,u,deep+);siz[u]+=siz[e];

         if(!son[u]||siz[son[u]]<siz[e])son[u]=e;

     }

 }

 void dfs2(int u,int tp){

     top[u]=tp,id[u]=++tid,posi[tid]=u;

     if(!son[u])return;dfs2(son[u],tp);

     for(int i=head[u];~i;i=node[i].nxt){

         int e=node[i].to;

         if(!id[e])dfs2(e,e);

     }

 }

 LL query(int rt,int l,int r){

     if(L<=l&&r<=R)return seg[rt];

     int mid=l+r>>;LL temp=;

     if(L<=mid)temp+=query(lson);

     if(R>mid) temp+=query(rson);

     return temp;

 }

 void update(int rt,int l,int r,LL v){

     if(l==r){seg[rt]=v;return;}

     int mid=l+r>>;

     if(L<=mid)update(lson,v);

     else update(rson,v);

     seg[rt]=seg[rt<<]+seg[rt<<|];

 }

 void lca(int x,int y){

     LL res=;

     while(top[x]!=top[y]){

         if(dep[top[x]]<dep[top[y]])swap(x,y);

         L=id[top[x]],R=id[x];

         res+=query(,,n);

         x=fa[top[x]];

     }

     if(dep[x]<dep[y])swap(x,y);

     L=id[y]+,R=id[x];   ///注意L +1

     if(x!=y)res+=query(,,n);

     printf("%lld\n",res);

 }

 void init(){

     mst(head,-);hcnt=tid=;

     mst(siz,);mst(son,);mst(id,);

 }

 int main(){

     int i,j,group,x,y,v,Case=;

     while(scanf("%d%d",&n,&m)!=EOF){

         init();

         for(i=;i<n;++i){

             x=read(),y=read(),v=read();

             edge[i].x=x,edge[i].y=y,edge[i].v=v;

             node[hcnt].v=v,node[hcnt].to=y,node[hcnt].nxt=head[x],head[x]=hcnt++;

             node[hcnt].v=v,node[hcnt].to=x,node[hcnt].nxt=head[y],head[y]=hcnt++;

         }

         dfs1(,,);dfs2(,);

         for(i=;i<n;++i){

             if(dep[edge[i].x]<dep[edge[i].y])swap(edge[i].x,edge[i].y);

             L=id[edge[i].x];

             update(,,n,edge[i].v);

         }

         while(m--){

             x=read();

             if(x==){

                 x=read(),y=read();

                 L=id[edge[x].x];

                 update(,,n,y);

             }

             else{

                 x=read(),y=read();

                 lca(x,y);

             }

         }

     }

     return ;

 }