Accept: 875 Submit: 2839
Time Limit: 1000 mSec Memory Limit : 32768
KB
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<cstdio> #include<cstring> #include<queue> #include<set> #include<map> #include<vector> #include<stack> #include<cmath> #include<string> #include<algorithm> using namespace std; typedef long long ll; const int sigma_size=26; const int N=100+50; const int MAXN=50000+50; const int inf=0x3fffffff; const double eps=1e-8; const int mod=100000000+7; #define L(x) (x<<1) #define R(x) (x<<1|1) #define PII pair<int, int> #define mk(x,y) make_pair((x),(y)) int n,m,edge_cnt,cnt; int head[MAXN],sz[MAXN],son[MAXN],fa[MAXN],top[MAXN],dep[MAXN],pos[MAXN]; struct Edge{ int u,v,w,next; }edge[MAXN<<1]; struct node{ int l,r; ll sum; }segtree[MAXN<<2]; void init(){ edge_cnt=cnt=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int w){ edge[edge_cnt].u=u; edge[edge_cnt].v=v; edge[edge_cnt].w=w; edge[edge_cnt].next=head[u]; head[u]=edge_cnt++; } void dfs1(int u,int pre,int depth){ sz[u]=1; son[u]=0; dep[u]=depth; fa[u]=pre; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(v == pre) continue; dfs1(v,u,depth+1); sz[u]+=sz[v]; if(sz[son[u]]<sz[v]) son[u]=v; } } void dfs2(int u,int tp){ pos[u]=cnt++; top[u]=tp; if(son[u]!=0) dfs2(son[u],top[u]); for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(v == fa[u] || v == son[u]) continue; dfs2(v,v); } } void build(int rt,int l,int r){ segtree[rt].l=l; segtree[rt].r=r; segtree[rt].sum=0; if(l == r) return ; int mid=(l+r)>>1; build(L(rt),l,mid); build(R(rt),mid+1,r); } void push_up(int rt){ segtree[rt].sum=segtree[L(rt)].sum+segtree[R(rt)].sum; } void update(int rt,int p,int x){ if(segtree[rt].l == segtree[rt].r){ segtree[rt].sum=x; return ; } int mid=(segtree[rt].l+segtree[rt].r)>>1; if(p<=mid) update(L(rt),p,x); else update(R(rt),p,x); push_up(rt); } ll query(int rt,int l,int r){ if(segtree[rt].l == l && segtree[rt].r == r) return segtree[rt].sum; int mid=(segtree[rt].l+segtree[rt].r)>>1; if(r<=mid) return query(L(rt),l,r); else if(l>mid) return query(R(rt),l,r); else return query(L(rt),l,mid)+query(R(rt),mid+1,r); } ll solve(int u,int v){ ll ans=0; while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]]) swap(u,v); ans+=query(1,pos[top[u]],pos[u]); u=fa[top[u]]; } if(dep[u]>dep[v]) swap(u,v); if(u!=v) ans+=query(1,pos[u]+1,pos[v]); return ans; } int main(){ while(~scanf("%d%d",&n,&m)){ init(); for(int i=1;i<n;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } dfs1(1,1,1); dfs2(1,1); build(1,1,n-1); for(int i=0;i<edge_cnt;i+=2){ int u=edge[i].u,v=edge[i].v,w=edge[i].w; if(dep[u]<dep[v]) swap(u,v); update(1,pos[u],w); } for(int i=0;i<m;i++){ int id,u,v; scanf("%d",&id); if(id == 0){ int x,w; scanf("%d%d",&x,&w); x=(x-1)*2; u=edge[x].u; v=edge[x].v; if(dep[u]<dep[v]) swap(u,v); update(1,pos[u],w); } else{ scanf("%d%d",&u,&v); printf("%lld ",solve(u,v)); } } } }