首页 > 代码库 > BZOJ 2836 魔法树
BZOJ 2836 魔法树
练手。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxv 100500 #define maxe 200500 using namespace std; long long n,q,x,y,z,g[maxv],nume=1,dis[maxv],top[maxv],fath[maxv],son[maxv],size[maxv],dfn[maxv],mx[maxv],times=0; struct edge { long long v,nxt; }e[maxe]; long long ls[maxv<<2],rs[maxv<<2],val[maxv<<2],lazy[maxv<<2],sum[maxv<<2],tot=0,root; char s[10]; void addedge(long long u,long long v) { e[++nume].v=v; e[nume].nxt=g[u]; g[u]=nume; } void dfs1(long long x) { size[x]=1;son[x]=0; for (long long i=g[x];i;i=e[i].nxt) { long long v=e[i].v; if (v!=fath[x]) { fath[v]=x;dis[v]=dis[x]+1; dfs1(v); size[x]+=size[v]; if (size[son[x]]<size[v]) son[x]=v; } } } void dfs2(long long x,long long father) { top[x]=father;dfn[x]=mx[x]=++times; if (son[x]) {dfs2(son[x],father);mx[x]=max(mx[x],mx[son[x]]);} for (long long i=g[x];i;i=e[i].nxt) { long long v=e[i].v; if ((v!=fath[x]) && (v!=son[x])) { dfs2(v,v); mx[x]=max(mx[x],mx[v]); } } } void build(long long &now,long long left,long long right) { now=++tot; if (left==right) return; long long mid=(left+right)>>1; build(ls[now],left,mid); build(rs[now],mid+1,right); } void pushdown(long long now,long long left,long long right) { if (!lazy[now]) return; long long mid=(left+right)>>1; lazy[ls[now]]+=lazy[now];sum[ls[now]]+=(mid-left+1)*lazy[now]; lazy[rs[now]]+=lazy[now];sum[rs[now]]+=(right-mid)*lazy[now]; lazy[now]=0; } void modify(long long now,long long left,long long right,long long l,long long r,long long val) { pushdown(now,left,right); if ((left==l) && (right==r)) { lazy[now]+=val;sum[now]+=(right-left+1)*val; return; } long long mid=(left+right)>>1; if (r<=mid) modify(ls[now],left,mid,l,r,val); else if (l>=mid+1) modify(rs[now],mid+1,right,l,r,val); else { modify(ls[now],left,mid,l,mid,val); modify(rs[now],mid+1,right,mid+1,r,val); } sum[now]=sum[ls[now]]+sum[rs[now]]; } void add() { long long f1=top[x],f2=top[y]; while (f1!=f2) { if (dis[f1]<dis[f2]) {swap(f1,f2);swap(x,y);} modify(root,1,n,dfn[f1],dfn[x],z); x=fath[f1];f1=top[x]; } if (dis[x]>dis[y]) swap(x,y); modify(root,1,n,dfn[x],dfn[y],z); } long long query(long long now,long long left,long long right,long long l,long long r) { pushdown(now,left,right); if ((left==l) && (right==r)) return sum[now]; long long mid=(left+right)>>1; if (r<=mid) return query(ls[now],left,mid,l,r); else if (l>=mid+1) return query(rs[now],mid+1,right,l,r); else return query(ls[now],left,mid,l,mid)+query(rs[now],mid+1,right,mid+1,r); } void ask() { printf("%lld\n",query(root,1,n,dfn[x],mx[x])); } int main() { scanf("%lld",&n); for (long long i=1;i<=n-1;i++) { scanf("%lld%lld",&x,&y);x++;y++; addedge(x,y);addedge(y,x); } dfs1(1); dfs2(1,1); build(root,1,n); scanf("%lld",&q); for (long long i=1;i<=q;i++) { scanf("%s",s); if (s[0]==‘A‘) { scanf("%lld%lld%lld",&x,&y,&z);x++;y++; add(); } else { scanf("%lld",&x);x++; ask(); } } return 0; }
BZOJ 2836 魔法树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。