锐客网

  1. 首页 > it技术 > >

FZU - 2082 过路费（树链剖分）

点我看题
题意：题目已经描述的很清晰了嘛～
分析：数链剖分模板题
参考代码：
【FZU - 2082 过路费（树链剖分）】

#include #include #include #include #includeusing namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define lson rt<<1 #define rson rt<<1|1 typedef long long ll; const int maxn = 5e4+10; int n,m; int e[maxn][3]; int head[maxn],tot; struct Edge{ int to,next; }; Edge edge[maxn]; int poi; int fa[maxn],son[maxn],siz[maxn],dep[maxn]; int p[maxn],fp[maxn],top[maxn]; int a[maxn]; //线段树，单点更新，区间查询 int sum[maxn<<2]; void Init() { tot = poi = 0; mem(head,-1); mem(son,-1); }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) { siz[u] = 1; fa[u] = pre; dep[u] = d; for( int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].to; if( v != pre) { dfs1(v,u,d+1); siz[u] += siz[v]; if( son[u] == -1 || siz[v] > siz[son[u]]) son[u] = v; } } }void dfs2( int u, int tp) { p[u] = ++poi; fp[p[u]] = u; top[u] = tp; if( son[u] == -1) return; 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]) dfs2(v,v); } }void PushUp( int rt) { sum[rt] = sum[lson]+sum[rson]; }void Build( int l, int r, int rt) { if( l == r) { //sum[rt] = a[l]; return; } int mid = (l+r)>>1; Build(l,mid,lson); Build(mid+1,r,rson); //PushUp(rt); }void Update( int l, int r, int rt, int pos, int val) { if( l == pos && r == pos) { sum[rt] = val; return; } int mid = (l+r)>>1; if( pos <= mid) Update(l,mid,lson,pos,val); else Update(mid+1,r,rson,pos,val); PushUp(rt); }ll Query( int l, int r, int rt, int L, int R) { if( l == L && r == R) return sum[rt]; int mid = (l+r)>>1; if( R <= mid) return Query(l,mid,lson,L,R); else if( L > mid) return Query(mid+1,r,rson,L,R); else return Query(l,mid,lson,L,mid)+Query(mid+1,r,rson,mid+1,R); }ll Find( int u, int v) { ll ans = 0; int t1 = top[u]; int t2 = top[v]; while( t1 != t2) { if( dep[t1] < dep[t2]) { swap(u,v); swap(t1,t2); } ans += Query(1,poi,1,p[t1],p[u]); u = fa[t1]; t1 = top[u]; } if( u == v) return ans; if( dep[u] > dep[v]) swap(u,v); return ans+Query(1,poi,1,p[son[u]],p[v]); }int main() { while( ~scanf("%d%d",&n,&m)) { Init(); for( int i = 1; i < n; 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); dfs2(1,1); Build(1,poi,1); for( int i = 1; i < n; i++) { if( dep[e[i][0]] > dep[e[i][1]]) swap(e[i][0],e[i][1]); Update(1,poi,1,p[e[i][1]],e[i][2]); a[p[e[i][1]]] = e[i][2]; } //Build(1,poi,1); while( m--) { int op,a,b; scanf("%d%d%d",&op,&a,&b); if( op == 0) Update(1,poi,1,p[e[a][1]],b); else if( op == 1) printf("%lld\n",Find(a,b)); } }return 0; }



    推荐阅读


    上一篇：Android注解库——support-annotations

    下一篇：activiti|springboot + activiti 项目搭建及简单使用