Problem Description 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 Sample Output Source
边权，单点修改，区间求和。
代码：
/* ***********************************************
Author :xianxingwuguan
Created Time :2014/3/1 10:06:18
File Name :1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=60010;
struct Edge{
int next,to;
}edge[2*maxn];
int head[maxn],tot;
int top[maxn];
int fa[maxn];
int deep[maxn];
int num[maxn];
int p[maxn],fp[maxn],son[maxn],pos;
void init(){
tot=0;
memset(head,-1,sizeof(head));
pos=0;
memset(son,-1,sizeof(son));
}
void addedge(int u,int v){
edge[tot].to=v;
edge[tot].next=head[u];
head[u]=tot++;
}
void dfs1(int u,int pre,int d){
deep[u]=d;
fa[u]=pre;
num[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(v==pre)continue;
dfs1(v,u,d+1);
num[u]+=num[v];
if(son[u]==-1||num[v]>num[son[u]])
son[u]=v;
}
}
void getpos(int u,int sp){
top[u]=sp;
p[u]=pos++;
fp[p[u]]=u;
if(son[u]==-1)return;
getpos(son[u],sp);
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(v!=son[u]&&v!=fa[u])
getpos(v,v);
}
}
struct Node{
int l,r,sum;
}tree[7*maxn];
void build(int i,int l,int r){
tree[i].l=l;
tree[i].r=r;
tree[i].sum=0;
if(l==r)return;
int mid=(l+r)/2;
build(2*i,l,mid);
build(2*i+1,mid+1,r);
}
void pushup(int i){
tree[i].sum=tree[2*i].sum+tree[2*i+1].sum;
}
void update(int i,int k,int val){
if(tree[i].l==tree[i].r){
tree[i].sum=val;
return;
}
int mid=(tree[i].l+tree[i].r)>>1;
if(k<=mid)update(2*i,k,val);
else update(2*i+1,k,val);
pushup(i);
}
int query(int i,int l,int r){
if(tree[i].l>=l&&tree[i].r<=r)return tree[i].sum;
int mid=(tree[i].l+tree[i].r)/2;
int ans=0;
if(l<=mid)ans+=query(2*i,l,r);
if(r>mid)ans+=query(2*i+1,l,r);
return ans;
}
int find(int u,int v){
int f1=top[u],f2=top[v];
int tmp=0;
while(f1!=f2){
if(deep[f1]<deep[f2])
swap(f1,f2),swap(u,v);
tmp+=query(1,p[f1],p[u]);
u=fa[f1];f1=top[u];
}
if(u==v)return tmp;
if(deep[u]>deep[v])swap(u,v);
return tmp+query(1,p[son[u]],p[v]);
}
int e[maxn][3];
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int n,m;
while(~scanf("%d%d",&n,&m)){
init();
for(int i=0;i<n-1;i++){
scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]);
addedge(e[i][0],e[i][1]);
addedge(e[i][1],e[i][0]);
}
dfs1(1,0,0);
getpos(1,1);
build(1,0,pos-1);
for(int i=0;i<n-1;i++){
if(deep[e[i][0]]>deep[e[i][1]])
swap(e[i][0],e[i][1]);
update(1,p[e[i][1]],e[i][2]);
}
while(m--){
int op,a,b;
scanf("%d%d%d",&op,&a,&b);
if(op==0)update(1,p[e[a-1][1]],b);
else printf("%d\n",find(a,b));
}
}
return 0;
}
原文：http://blog.csdn.net/xianxingwuguan1/article/details/20211433