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
对于每个询问操作, 输出该询问的答案. 答案之间用换行隔开.
- Sample Input
- 5 5
- 1 2 3 4 5
- 1 2
- 1 4
- 2 3
- 2 5
- 3 3
- 1 2 1
- 3 5
- 2 1 2
- 3 3
- Sample Output
- 6 9 13
- HINT
对于 100% 的数据, N,M<=100000 , 且所有输入数据的绝对值都不会超过 10^6 .
solution
树剖板子题, 或者线段树直接维护欧拉序也行.
- #include<bits/stdc++.h>
- #define int long long
- using namespace std;
- void read(int &x) {
- x=0;int f=1;char ch=getchar();
- for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
- for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
- }
- void print(int x) {
- if(x<0) x=-x,putchar('-');
- if(!x) return ;print(x/10),putchar(x%10+48);
- }
- void write(int x) {if(!x) putchar('0');else print(x);puts("");}
- const int maxn = 1e5+10;
- int n,m,head[maxn],hs[maxn],top[maxn],dfn[maxn],dep[maxn],sz[maxn],dfn_cnt,f[maxn],val[maxn],tot;
- struct edge{int to,nxt;}e[maxn<<1];
- void add(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}
- void ins(int u,int v) {add(u,v),add(v,u);}
- #define ls p<<1
- #define rs p<<1|1
- #define mid ((l+r)>>1ll)
- struct Segment_Tree {
- int tr[maxn<<2],tag[maxn<<2];
- void update(int p) {tr[p]=tr[ls]+tr[rs];}
- void pushdown(int p,int l,int r) {
- if(!tag[p]) return ;
- tag[ls]+=tag[p],tag[rs]+=tag[p];
- tr[ls]+=tag[p]*(mid-l+1),tr[rs]+=tag[p]*(r-mid);tag[p]=0;
- }
- void modify(int p,int l,int r,int x,int y,int v) {
- if(x<=l&&r<=y) return tag[p]+=v,tr[p]+=v*(r-l+1),void();
- pushdown(p,l,r);
- if(x<=mid) modify(ls,l,mid,x,y,v);
- if(y>mid) modify(rs,mid+1,r,x,y,v);
- update(p);
- }
- int query(int p,int l,int r,int x,int y) {
- if(x<=l&&r<=y) return tr[p];
- pushdown(p,l,r);int ans=0;
- if(x<=mid) ans+=query(ls,l,mid,x,y);
- if(y>mid) ans+=query(rs,mid+1,r,x,y);
- return ans;
- }
- }SGT;
- struct Heavy_Light_Decomposition {
- void dfs1(int x,int fa) {
- dep[x]=dep[fa]+1;sz[x]=1;f[x]=fa;
- for(int i=head[x];i;i=e[i].nxt)
- if(e[i].to!=fa) {
- dfs1(e[i].to,x),sz[x]+=sz[e[i].to];
- if(sz[hs[x]]<sz[e[i].to]) hs[x]=e[i].to;
- }
- }
- void dfs2(int x) {
- dfn[x]=++dfn_cnt;
- if(hs[f[x]]==x) top[x]=top[f[x]];
- else top[x]=x;
- if(hs[x]) dfs2(hs[x]);
- for(int i=head[x];i;i=e[i].nxt)
- if(e[i].to!=f[x]&&e[i].to!=hs[x]) dfs2(e[i].to);
- }
- int query(int x) {
- int ans=0;
- while(x) {
- ans+=SGT.query(1,1,n,dfn[top[x]],dfn[x]);
- x=f[top[x]];
- }
- return ans;
- }
- }HLD;
- signed main() {
- read(n),read(m);
- for(int i=1;i<=n;i++) read(val[i]);
- for(int i=1,x,y;i<n;i++) read(x),read(y),ins(x,y);
- HLD.dfs1(1,0),HLD.dfs2(1);
- for(int i=1;i<=n;i++) SGT.modify(1,1,n,dfn[i],dfn[i],val[i]);
- for(int op,x,y,i=1;i<=m;i++) {
- read(op);
- if(op==1) read(x),read(y),SGT.modify(1,1,n,dfn[x],dfn[x],y);
- else if(op==2) read(x),read(y),SGT.modify(1,1,n,dfn[x],dfn[x]+sz[x]-1,y);
- else read(x),write(HLD.query(x));
- }
- return 0;
- }
[bzoj4034] [HAOI2015] 树上操作
来源: http://www.bubuko.com/infodetail-2889675.html