题目链接：http://acm.fzu.edu.cn/problem.php?pid=2082
wushen博客：wuyiqi
思路：
边权转点权：
由于线段树中的点是节点，则把题目给的边权值作为 边一端 距离根更远的节点的点权值。
直接设置根权值为0 这样不会影响题意。
因为求的的是两点间所有的点权和，所以要减去 LCA(u,v)，因为这个点所代表的边是没有在路径上的。
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
#define N 50050
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define Mid(x,y) ((x+y)>>1)
#define ll __int64
struct Edge{
ll from, to, dis,nex;
bool yes;
}edge[N<<1];
ll head[N], edgenum;
ll dis[N];
void addedge(ll u, ll v, ll d){
Edge E={u,v,d,head[u],false};
edge[edgenum] = E;
head[u] = edgenum++;
}
ll son[N];
ll top[N];
ll fp[N];
ll p[N];
ll siz[N];
ll dep[N];
ll fa[N];
ll tree_id;
void dfs(ll u, ll father, ll deep){
fa[u] = father; dep[u] = deep;
siz[u] = 1;
for(ll i = head[u]; ~i; i = edge[i].nex){
ll v = edge[i].to; if(v == father)continue;
dfs(v, u, deep+1);
siz[u] += siz[v];
if(son[u] == -1 || siz[son[u]]<siz[v])son[u] = v;
dis[v] = edge[i].dis;
edge[i].yes = true;
}
}
void getpos(ll u, ll toppos){
p[u] = tree_id++; fp[p[u]] = u;
top[u] = toppos;
if(son[u] == -1)return;
if(u==0)getpos(son[u],son[u]);
else getpos(son[u], toppos);
for(int i = head[u]; ~i; i = edge[i].nex)
{
int v = edge[i].to; if(v == fa[u] || v == son[u])continue;
getpos(v,v);
}
}
struct node{
ll l, r;
ll sum;
}tree[N*8];
void updata_up(ll id){
tree[id].sum = tree[L(id)].sum+tree[R(id)].sum;
}
void build(ll l, ll r, ll id){
tree[id].l = l, tree[id].r = r;
tree[id].sum = 0;
if(l == r)return ;
int mid = Mid(l,r);
build(l,mid,L(id)), build(mid+1,r,R(id));
}
void updata(ll pos, ll val, ll id){
if(tree[id].l == tree[id].r)
{
tree[id].sum = val;
return;
}
ll mid = Mid(tree[id].l,tree[id].r);
if(pos <= mid)updata(pos, val, L(id));
else updata(pos, val, R(id));
updata_up(id);
}
ll query(ll l, ll r, ll id){
if(l <= tree[id].l && tree[id].r <= r)return tree[id].sum;
ll mid = Mid(tree[id].l, tree[id].r);
ll ans = 0;
if(l <= mid)ans+=query(l,r,L(id));
if(r > mid)ans+=query(l,r,R(id));
return ans;
}
ll Query(ll x,ll y){ //让x在y下面
ll f1 = top[x], f2 = top[y];
ll ans = 0;
while(f1 != f2)
{
if(dep[f1]<dep[f2])swap(f1,f2),swap(x,y);
ans += query(p[f1],p[x],1);
x = fa[f1];
f1 = top[x];
}
if(dep[x] > dep[y])swap(x,y);
return ans + query(p[x],p[y],1) - query(p[x],p[x],1);;
}
void change(ll pos, ll val){
Edge &E = edge[pos<<1]; if(E.yes == false) E = edge[pos<<1|1];
E.dis = val;
updata(p[E.to], val, 1);
}
ll n, m;
void init(){
memset(head, -1, sizeof(head)), edgenum = 0;
memset(son, -1, sizeof(son));
tree_id = 1;
}
int main(){
ll i, j, u, v, d;
while(~scanf("%I64d %I64d",&n,&m))
{
init();
for(i = 1; i < n; i++) {
scanf("%I64d %I64d %I64d",&u,&v,&d);
addedge(u,v,d);
addedge(v,u,d);
}
dfs(1,1,0);
getpos(1,1);
build(1,n,1); //建立虚拟根节点1
updata(p[1],0,1);
for(i = 2; i <= n; i++) updata(p[i],dis[i],1);
while(m--)
{
scanf("%I64d %I64d %I64d",&d,&u,&v);
if(d == 0)change(u-1,v);
else printf("%I64d\n",Query(u,v));
}
}
return 0;
}
/*
7 99
7 1 1
1 2 2
1 3 3
2 6 4
2 4 5
3 5 6
1 6 3
1 2 5
1 4 5
1 1 5
1 7 5
0 1 100
1 7 5
0 6 100
1 3 5
1 5 3
1 5 4
*/FZU 2082 求树上任意点间距离 边权转为点权 树链剖分,布布扣,bubuko.com
FZU 2082 求树上任意点间距离 边权转为点权 树链剖分
原文：http://blog.csdn.net/acmmmm/article/details/20242349