过路费 Time Limit: 1000MS Memory Limit: 32768KB 64bit IO Format: %I64d & %I64u
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月（校赛热身赛）
基于边权的链剖。。。 这道题本来是求和的，所以可以采用边权放到点权上，这里为了练普遍情况，采用线段表示边。。 那么线段树里面判断的时候要分别-1 +1 ， 因为区间必须包含线段才进行更新，递归下去的时候却要m，这样才能保证包含进去。 不过注意特判x==y的情况，比如正好查询top到top之间的和。 另外，modify和query都不支持跨链的操作，所以更新的时候最特别的那种情况要在road里面二分查找（用link数组快速查询原边的位置）。 最后网上说需要扩栈，亲测不用。
由于是求和，所以也可以用dfs+前缀和+LCA来做。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<vector> #include<queue> #include<stack> #include<map> #include<set> #include<string> #include<iomanip> #include<ctime> #include<climits> #include<cctype> #include<algorithm> #ifdef WIN32 #define AUTO "%I64d" #else #define AUTO "%lld" #endif using namespace std; #define smax(x,tmp) x=max((x),(tmp)) #define smin(x,tmp) x=min((x),(tmp)) #define maxx(x1,x2,x3) max(max(x1,x2),x3) #define minn(x1,x2,x3) min(min(x1,x2),x3) typedef long long LL; const int INF=0x3f3f3f3f; const int maxn = 50005; struct Edge { int to,next; }edge[maxn<<1]; int head[maxn]; int maxedge; inline void addedge(int u,int v) { edge[++maxedge] = (Edge) { v,head[u] }; head[u] = maxedge; edge[++maxedge] = (Edge) { u,head[v] }; head[v] = maxedge; } struct Road { int u,v; int c; int order; bool operator < (const Road t) const { if(u ^ t.u) return u < t.u; return v < t.v; } }road[maxn]; int link[maxn]; int son[maxn],fa[maxn],size[maxn],depth[maxn]; int top[maxn],id[maxn],rid[maxn]; LL sum[maxn<<2]; int maxnode; int n,q; inline int find(int u,int v) { if(u>v) swap(u,v); Road t; t.u=u,t.v=v; return lower_bound(road+1,road+n,t) - road; } void dfs1(int u,int father,int deep) { depth[u]=deep; fa[u]=father; size[u]=1; for(int i=head[u];~i;i=edge[i].next) { int v=edge[i].to; if(v==father) continue; dfs1(v,u,deep+1); size[u]+=size[v]; if(!son[u] || size[son[u]]<size[v]) son[u]=v; } } void dfs2(int u,int tp) { top[u]=tp; id[u]=++maxnode; rid[maxnode]=u; if(son[u]) dfs2(son[u],tp); for(int i=head[u];~i;i=edge[i].next) { int v=edge[i].to; if(v==fa[u] || v==son[u]) continue; dfs2(v,v); } } inline bool init() { if(!~scanf("%d%d",&n,&q)) return false; memset(head,-1,sizeof(head)); maxedge=-1; memset(son,0,sizeof(son)); memset(id,0,sizeof(id)); memset(rid,0,sizeof(rid)); maxnode=0; for(int i=1;i<n;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); if(x>y) swap(x,y); road[i].u=x,road[i].v=y,road[i].c=z; road[i].order=i; addedge(x,y); } sort(road+1,road+n); for(int i=1;i<n;i++) link[road[i].order]=i; dfs1(1,-1,1); dfs2(1,1); return true; } inline void update(int root) { sum[root] = sum[root<<1] + sum[root<<1|1]; } void build(int root,int l,int r) { if(l+1==r) { if(top[rid[l]] == top[rid[r]]) sum[root]=road[find(rid[l],rid[r])].c; return; } int m=(l+r)>>1; build(root<<1,l,m); build(root<<1|1,m,r); update(root); } void modify(int root,int l,int r,int x,int y,int val) { if(x==y) return; if(l==x && y==r) { sum[root]=val; return; } int m=(l+r)>>1; if(x<=m-1 && l<=y) modify(root<<1,l,m,x,y,val); else modify(root<<1|1,m,r,x,y,val); update(root); } void Change(int pos,int val) { int t1=road[link[pos]].u,t2=road[link[pos]].v; if(id[t1]>id[t2]) swap(t1,t2); if(top[t1] == top[t2]) modify(1,1,maxnode,id[t1],id[t2],val); road[link[pos]].c=val; } LL query(int root,int l,int r,int x,int y) { if(x==y) return 0ll; // special judge needed!!!! if(x<=l && r<=y) return sum[root]; int m=(l+r)>>1; LL ret=0ll; if(x<=m-1 && l<=y) ret += query(root<<1,l,m,x,y); if(y>=m+1 && r>=x) ret += query(root<<1|1,m,r,x,y); return ret; } LL FindSum(int u,int v) { LL ret=0ll; int t1=top[u],t2=top[v]; while(t1^t2) { if(depth[t1]<depth[t2]) swap(t1,t2),swap(u,v); ret += query(1,1,maxnode,id[t1],id[u]); ret += road[find(t1,fa[t1])].c; u=fa[t1]; t1=top[u]; } if(depth[u]<depth[v]) swap(u,v); ret += query(1,1,maxnode,id[v],id[u]); return ret; } int main() { #ifndef ONLINE_JUDGE freopen("fee.in","r",stdin); freopen("fee.out","w",stdout); #else #pragma comment(linker, "/STACK:1024000000 1024000000") #endif while(init()) { build(1,1,maxnode); while(q--) { int opt,x,y; scanf("%d%d%d",&opt,&x,&y); if(opt) printf(AUTO "\n",FindSum(x,y)); else Change(x,y); } } return 0; }