首页 > 代码库 > foj 2082 树链剖分 第2天
foj 2082 树链剖分 第2天
擦,没啥好说的,这个模板至少得打10遍。。纪念自己成功的打错了。。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define LL int #define lson id << 1 #define rson id << 1|1 const LL M = 100008; LL ti[M],top[M],siz[M],son[M],father[M],tp,idx,dep[M]; struct Linetree{ LL sum,l,r,mark; LL mid(){ return (l+r)/2; } }node[M*4]; struct { LL head; }H[M]; struct { LL v,next; }E[M]; void add(LL u,LL v){ E[tp].v = v; E[tp].next = H[u]. head; H[u].head = tp++; } void dfs_1(LL u,LL fa){ son[u] = 0;siz[u] = 1;father[u] = fa; dep[u] = dep[fa] + 1; for(LL i=H[u].head;i!=-1;i=E[i].next){ LL v = E[i].v; if(v == fa)continue; dfs_1(v,u); siz[u] += siz[v]; if(siz[v] > siz[son[u]])son[u] = v ; } } void dfs_2(LL u,LL fa){ ti[u] = idx++; top[u] = fa; if(son[u])dfs_2(son[u],fa); for(LL i=H[u].head;i!=-1;i = E[i].next){ LL v = E[i].v; if(v == father[u]||v == son[u]) continue; dfs_2(v,v); } } /* 线段树*/ void build_tree(LL id,LL l,LL r){ node[id].l = l; node[id].r = r; node[id].sum = 0; if(l == r) return; LL mid = node[id].mid(); build_tree(lson,l,mid); build_tree(rson,mid+1,r); } void push_up(LL id){ node[id].sum = node[lson].sum + node[rson].sum; } void update(LL id,LL k,LL w){ if(node[id].l == k&&node[id].r == k){ node[id].sum = w; return; } LL mid = node[id].mid(); if(k <=mid)update(lson,k,w); else update(rson,k,w); push_up(id); } LL query(LL id,LL l,LL r){ if(node[id].l == l && node[id].r == r) return node[id].sum; LL mid = node[id].mid(); if(r <=mid )return query(lson,l,r); else if(l > mid)return query(rson,l,r); else { return query(lson,l,mid) + query(rson,mid+1,r); } } LL e[M][4]; LL findmax(LL u,LL v){ LL f1 = top[u]; LL f2 = top[v]; int sum = 0; while(f1 != f2){ if(dep[f1] < dep[f2]){ swap(f1,f2);swap(u,v); } sum += query(1,ti[f1],ti[u]); u = father[f1];f1 = top[u]; } if(u == v) return sum; if(dep[u] > dep[v] ) swap(u,v); sum += query(1,ti[son[u]],ti[v]); return sum; } void init(){ memset(E,-1,sizeof(E)); memset(H,-1,sizeof(H)); tp = 0; idx = 0; memset(son,0,sizeof(son)); } int main(){ //freopen("input.txt","r",stdin); LL n,m,u,v,w; while(~scanf("%d%d",&n,&m)){ init(); for(LL i=0;i<n-1;i++){ scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]); add(e[i][0],e[i][1]); add(e[i][1],e[i][0]); } dfs_1(1,1); dfs_2(1,1); build_tree(1,1,idx-1); for(LL i=0;i<n-1;i++){ if(dep[e[i][0]] > dep[e[i][1]]) swap(e[i][0],e[i][1]); update(1,ti[e[i][1]],e[i][2]); } while(m --){ scanf("%d%d%d",&w,&u,&v); if(w)printf("%d\n",findmax(u,v)); else update(1,ti[e[u-1][1]],v); } } }
foj 2082 树链剖分 第2天
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。