首页 > 代码库 > BZOJ 4034 【HAOI2015】 T2
BZOJ 4034 【HAOI2015】 T2
Description
有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：
操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。
Input
第一行包含两个整数 N, M 。表示点数和操作数。
接下来一行 N 个整数，表示树中节点的初始权值。
接下来 N-1 行每行三个正整数 fr, to ， 表示该树中存在一条边 (fr, to) 。
再接下来 M 行，每行分别表示一次操作。其中第一个数表示该操
作的种类（ 1-3 ） ，之后接这个操作的参数（ x 或者 x a ）
Output
对于每个询问操作，输出该询问的答案。答案之间用换行隔开
HINT
对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不会超过 10^6 。
很久没有写过树剖了……找个板子题出来熟悉一下。
树链剖分可以把树上的问题转化为序列上的问题，然后就可以用线段树等数据结构维护了。像这种不需要标记的区间修改、求值直接用树状数组就可以了。
贴一个板子：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define maxn 100010
using namespace std;
typedef long long llg;
int n,m,a[maxn],le[maxn],ri[maxn];
int head[maxn],to[maxn<<1],next[maxn<<1],tt;
int fa[maxn],top[maxn],siz[maxn],son[maxn],fc[maxn];
llg c1[maxn],c2[maxn];
int getint(){
int w=0;bool q=0;
char c=getchar();
while((c>‘9‘||c<‘0‘)&&c!=‘-‘) c=getchar();
if(c==‘-‘) c=getchar(),q=1;
while(c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar();
return q?-w:w;
}
void link(int x,int y){
to[++tt]=y;next[tt]=head[x];head[x]=tt;
to[++tt]=x;next[tt]=head[y];head[y]=tt;
}
inline void add(int x,int y){for(int i=x;i<=n;i+=i&(-i)) c1[i]+=y,c2[i]+=(llg)x*y;}
inline llg sum(int x){
llg ans(0);
for(int i=x;i;i-=i&(-i)) ans+=(llg)(x+1)*c1[i]-c2[i];
return ans;
}
void dfs(int u){
siz[u]=1;
for(int i=head[u],v;v=to[i],i;i=next[i])
if(v!=fa[u]){
fa[v]=u; dfs(v); siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs(int u,int dd){
top[u]=dd; le[u]=fc[u]=++tt;
add(tt,a[u]),add(tt+1,-a[u]);
if(son[u]) dfs(son[u],dd);
for(int i=head[u],v;v=to[i],i;i=next[i])
if(!top[v]) dfs(v,v);
ri[u]=tt;
}
llg work(int u){
llg ans=0;
while(u){
int L=fc[top[u]],R=fc[u];
ans+=sum(R)-sum(L-1);
u=fa[top[u]];
}
return ans;
}
int main(){
File("a");
n=getint(); m=getint();
for(int i=1;i<=n;i++) a[i]=getint();
for(int i=1;i<n;i++) link(getint(),getint());
tt=0; dfs(1); dfs(1,1);
while(m--){
int ty=getint(),u=getint(),x;
if(ty==3) printf("%lld\n",work(u));
else{
x=getint(); add(le[u],x);
if(ty==1) add(le[u]+1,-x);
else add(ri[u]+1,-x);
}
}
return 0;
}
BZOJ 4034 【HAOI2015】 T2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。