【BZOJ2836】魔法树

Description

Input

Output

Sample Input

4
0 1
1 2
2 3
4
Add 1 3 1
Query 0
Query 1
Query 2

Sample Output

3
3
2

题解:链剖裸题+1,一棵子树对应DFS序上的一段区间。然而又没有1A

#include <cstdio>
#include <cstring>
#include <iostream>
#define lson x<<1
#define rson x<<1|1
using namespace std;
const int maxn=100010;
int n,m,cnt;
typedef long long ll;
int to[maxn],next[maxn],head[maxn],p[maxn],q[maxn],siz[maxn],son[maxn],dep[maxn],top[maxn],fa[maxn];
ll s[maxn<<2],ts[maxn<<2];
char str[10];
int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
void dfs1(int x)
{
siz[x]=1;
for(int i=head[x];i!=-1;i=next[i])
{
fa[to[i]]=x,dep[to[i]]=dep[x]+1;
dfs1(to[i]);
siz[x]+=siz[to[i]];
if(siz[son[x]]<siz[to[i]]) son[x]=to[i];
}
}
void dfs2(int x,int tp)
{
top[x]=tp,p[x]=++p[0];
if(son[x]) dfs2(son[x],tp);
for(int i=head[x];i!=-1;i=next[i])
if(to[i]!=son[x])
dfs2(to[i],to[i]);
q[x]=p[0];
}
void pushdown(int l,int r,int x)
{
if(ts[x])
{
int mid=l+r>>1;
ts[lson]+=ts[x],ts[rson]+=ts[x],s[lson]+=(mid-l+1)*ts[x],s[rson]+=(r-mid)*ts[x];
ts[x]=0;
}
}
void pushup(int x)
{
s[x]=s[lson]+s[rson];
}
void updata(int l,int r,int x,int a,int b,ll v)
{
if(a<=l&&r<=b)
{
s[x]+=(r-l+1)*v,ts[x]+=v;
return ;
}
pushdown(l,r,x);
int mid=l+r>>1;
if(a<=mid) updata(l,mid,lson,a,b,v);
if(b>mid) updata(mid+1,r,rson,a,b,v);
pushup(x);
}
ll query(int l,int r,int x,int a,int b)
{
if(a<=l&&r<=b) return s[x];
pushdown(l,r,x);
int mid=l+r>>1;
if(b<=mid) return query(l,mid,lson,a,b);
if(a>mid) return query(mid+1,r,rson,a,b);
return query(l,mid,lson,a,b)+query(mid+1,r,rson,a,b);
}
void add(int a,int b)
{
to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;
}
void ADD(int x,int y,ll z)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
updata(1,n,1,p[top[x]],p[x],z);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
updata(1,n,1,p[x],p[y],z);
}
int main()
{
n=rd();
int i,a,b;
memset(head,-1,sizeof(head));
for(i=1;i<n;i++) a=rd()+1,b=rd()+1,add(a,b);
dep[1]=1,dfs1(1),dfs2(1,1);
m=rd();
for(i=1;i<=m;i++)
{
scanf("%s",str);
if(str[0]=='A') a=rd()+1,b=rd()+1,ADD(a,b,rd());
else a=rd()+1,printf("%lld\n",query(1,n,1,p[a],q[a]));
}
return 0;
}

最新文章

  1. JS中,!=, !== 和 !的区别和使用场景
  2. Google Map API Version3 :代码添加和删除marker标记
  3. EUI Scroller实现图片轮播 组件 ItemScroller
  4. 对象化前端表单(Form)提交
  5. js中的undefined与null、空值的比较
  6. C++编程命名规则(转载)
  7. 详解xml文件描述,读取方法以及将对象存放到xml文档中,并按照指定的特征寻找的方案
  8. Laravel 5 基础(十)- 日期,Mutator 和 Scope
  9. Asp.net MVC 4 异步方法
  10. DropBox与Box的区别,包括直接的投资人的评价(本地Sync可能还是挺重要的)
  11. android代码控制seekbar的样式
  12. python中关于汉诺塔问题和使用turtle库实现其搬运过程
  13. python——函数之装饰器
  14. ⌈洛谷4735⌋⌈BZOJ3261⌋最大异或和【可持久化01Trie】
  15. Mac 启动或者禁用翻盖自动开关机
  16. Linux下 查找大文件
  17. Java的学习03
  18. DDD-002
  19. Google Guava--基础工具用法
  20. SpringBoot入门 (五) 数据库访问之spring data jpa

热门文章

  1. thinkphp 编辑器kindeditor
  2. LINK : fatal error LNK1123: failure during conversion to COFF: file invalid or corrupt
  3. Linux下自动备份Oracle数据库并删除指定天数前的备份
  4. wx小程序的学习
  5. 修改System.Web.Mvc.WebViewPage创建自己的pageBase
  6. Atitit.判断汉字的编码 regedit 注册表里面的reg_sz
  7. Xilinx IP核使用(一)--FIFO
  8. https证书最佳实战目录
  9. ListView局部更新(非notifyDataSetChanged)
  10. redis命令_ZRANGE