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
Source
FOJ有奖月赛-2012年4月（校赛热身赛）题解
裸题
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define ls i<<1 #define rs ls | 1 #define mid ((ll+rr)>>1) #define pii pair<int,int> #define MP make_pair typedef long long LL; const long long INF = 1e18; const double Pi = acos(-1.0); const int N = 2e5+10, M = 5e5+11, inf = 2e9, mod = 998244353; struct edge{int to,next,value;}e[N * 2]; struct Lin {int u; int v; int w; Lin(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {} }L[N*2]; LL sum[N]; int head[N],t=1,f[N],q,n,top[N],siz[N],son[N],pos[N],val[N],deep[N],tot; void init() { t = 1; memset(head,0,sizeof(head)); deep[0] = 0; siz[0] = 0; f[1] = 0; tot = 0; } void add(int u,int v) {e[t].next=head[u];e[t].to=v;head[u]=t++;} void dfs1(int u,int fa) { siz[u] = 1; son[u] = 0; f[u] = fa; deep[u] = deep[fa] + 1; for(int i = head[u]; i; i = e[i].next) { int to = e[i].to; if(to == fa) continue; dfs1(to,u); siz[u] += siz[to]; if(siz[to] > siz[son[u]]) son[u] = to; } } void dfs2(int u,int chan) { top[u] = son[chan]==u?top[chan]:u; pos[u] = ++tot; if(son[u]) dfs2(son[u],u); for(int i = head[u]; i; i = e[i].next) { int to = e[i].to; if(to == son[u] || to == chan) continue; dfs2(to,u); } } void build(int i,int ll,int rr) { sum[i] = 0; if(ll == rr) { sum[i] = val[ll]; return ; } build(ls,ll,mid), build(rs,mid+1,rr); sum[i] = sum[ls] + sum[rs]; } void update(int i,int ll,int rr,int x,int c) { if(x == ll && x == rr) { sum[i] = c; return ; } if(x <= mid) update(ls,ll,mid,x,c); else update(rs,mid+1,rr,x,c); sum[i] = sum[ls] + sum[rs]; } LL query(int i,int ll,int rr,int x,int y) { if(x == ll && rr == y) { return sum[i]; } if(y <= mid) return query(ls,ll,mid,x,y); else if(x > mid) return query(rs,mid+1,rr,x,y); else return query(ls,ll,mid,x,mid) + query(rs,mid+1,rr,mid+1,y); } LL sub_query(int x,int y,LL ret = 0) { while (top[x] != top[y]) { if(deep[top[x]] < deep[top[y]]) swap(x,y); ret += query(1,1,n,pos[top[x]],pos[x]); x = f[top[x]]; } if(x == y) return ret; if(deep[x] > deep[y]) swap(x,y); return ret + query(1,1,n,pos[x]+1, pos[y]); } void solve() { init(); for(int i = 1; i <= n-1; ++i) { int a,b,c; scanf("%d%d%d",&a,&b,&c); L[i] = Lin(a,b,c); add(a,b);add(b,a); } dfs1(1,0); dfs2(1,0); val[1] = 0; for(int i = 1; i <= n-1; ++i) { if(deep[L[i].u] < deep[L[i].v]) swap(L[i].u, L[i].v); val[pos[L[i].u]] = L[i].w; }//cout<<1<<endl; build(1,1,n); while(q--){ int op,x,y; scanf("%d%d%d",&op,&x,&y); if(op == 0) update(1,1,n,pos[L[x].u],y); else printf("%I64d ",sub_query(x,y)); } } int main() { while(~scanf("%d%d",&n,&q)) {solve();}return 0; }