传送门

树剖板子……

一个路径加和,线段树上打标记。一个子树询问,dfs的时候记录一下子树的区间就行

 // luogu-judger-enable-o2
//minamoto
#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
inline int read(){
#define num ch-'0'
char ch;bool flag=;int res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
inline char getop(){char ch;while((ch=getc())!='A'&&ch!='Q');return ch;}
char sr[<<],z[];int C=-,Z;
inline void Ot(){fwrite(sr,,C+,stdout),C=-;}
inline void print(ll x){
if(C><<)Ot();if(x<)sr[++C]=,x=-x;
while(z[++Z]=x%+,x/=);
while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=1e5+;
int head[N],Next[N],ver[N],tot;
inline void add(int u,int v){
ver[++tot]=v,Next[tot]=head[u],head[u]=tot;
}
int L[N],R[N],top[N],fa[N],dep[N],sz[N],son[N],cnt,n,m;
void dfs1(int u){
sz[u]=,dep[u]=dep[fa[u]]+;
for(int i=head[u];i;i=Next[i]){
int v=ver[i];
fa[v]=u,dfs1(v),sz[u]+=sz[v];
if(sz[son[u]]<sz[v]) son[u]=v;
}
}
void dfs2(int u,int t){
top[u]=t,L[u]=++cnt;
if(son[u]){
dfs2(son[u],t);
for(int i=head[u];i;i=Next[i])
if(ver[i]!=son[u]) dfs2(ver[i],ver[i]);
}
R[u]=cnt;
// printf("%d %d %d %d\n",u,L[u],R[u],son[u]);
}
ll tag[N<<],sum[N<<];int size[N<<];
#define ls (p<<1)
#define rs (p<<1|1)
inline void upd(int p){sum[p]=sum[ls]+sum[rs];}
inline void pd(int p){
if(tag[p]){
tag[ls]+=tag[p],tag[rs]+=tag[p];
sum[ls]+=tag[p]*size[ls],sum[rs]+=tag[p]*size[rs];
tag[p]=;
}
}
void build(int p,int l,int r){
size[p]=r-l+;if(l==r) return;
int mid=(l+r)>>;
build(ls,l,mid),build(rs,mid+,r);
}
void update(int p,int l,int r,int ql,int qr,int x){
if(ql<=l&&qr>=r) return (void)(tag[p]+=x,sum[p]+=1ll*x*size[p]);
int mid=(l+r)>>;pd(p);
if(ql<=mid) update(ls,l,mid,ql,qr,x);
if(qr>mid) update(rs,mid+,r,ql,qr,x);
upd(p);
}
ll query(int p,int l,int r,int ql,int qr){
if(ql<=l&&qr>=r) return sum[p];
int mid=(l+r)>>;ll res=;pd(p);
if(ql<=mid) res+=query(ls,l,mid,ql,qr);
if(qr>mid) res+=query(rs,mid+,r,ql,qr);
return res;
}
void change(int u,int v,int x){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
update(,,n,L[top[u]],L[u],x),u=fa[top[u]];
}
if(dep[u]<dep[v]) swap(u,v);
update(,,n,L[v],L[u],x);
}
int main(){
// freopen("testdata.in","r",stdin);
n=read();
for(int i=,u,v;i<n;++i)
u=read()+,v=read()+,add(u,v);
dfs1(),dfs2(,),build(,,n);
m=read();
while(m--){
char op=getop();int u,v,d;
if(op=='A') u=read()+,v=read()+,d=read(),change(u,v,d);
else u=read()+,print(query(,,n,L[u],R[u]));
}
Ot();
return ;
}

最新文章

  1. PHP 文件与目录操作函数总结
  2. MongoDB csv文件导入导出
  3. logback使用总结
  4. Android Studio 中配置强大的版本管理系统
  5. oracle 直接客户端使用
  6. mvc与mvvm
  7. linux之utime函数解析
  8. openSuse快捷键
  9. 微信小程序跳一跳辅助程序(手动版)
  10. Vue(二十七)当前GitHub上排名前十的热门Vue项目(转载)
  11. 我和python的初相识
  12. Spring-AspectJ 配置文件
  13. [20190306]奇怪的查询结果.txt
  14. _mount_allowed
  15. C#语言————第四章 常用Convert类的类型转换方法
  16. python scrapy 登录知乎过程
  17. Python Tools for Machine Learning
  18. 《Pro SQL Server Internals, 2nd edition》的CHAPTER 2 Tables and Indexes中的Clustered Indexes一节(翻译)
  19. IDEA安全编码组件
  20. Easyui data方法扩展finder

热门文章

  1. Es首页
  2. Java的基本运算符
  3. react 使用 eslint 的三种代码检查方案总结,多了解点--让代码更完美....
  4. ModelAndView对象作用
  5. 我的Android Studio 优化之路
  6. Office2010,PPT,EXCEL如何插入日历控件
  7. 【Mongodb教程 第十一课 】MongoDB 聚合
  8. LoadRunner系列之—-04 录制基于https协议的脚本
  9. 【问题记录】LoadRunner 接口压测-json格式报文
  10. Codeforces 480B Long Jumps 规律题