题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4034
题意：
有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：操作 1 ：把某个节点 x 的点权增加 a 。操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。
直接链剖，子树在 dfs 序上一定是一段 [root,root+size-1] 的连续区间
1A 死因：long long
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 100010 #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,w[N],opt; struct zgz { int next,to; }edge[N<<1]; int cnt=1,head[N]; void add(int from,int to) { edge[cnt].to=to; edge[cnt].next=head[from]; head[from]=cnt++; } //--------------------read in the map-------------------------- int sz[N],son[N],fa[N]; void dfs1(int x,int f) { sz[x]=1; for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to; if(to==f)continue; fa[to]=x; dfs1(to,x); sz[x]+=sz[to]; if(sz[to]>sz[son[x]])son[x]=to; } } int top[N],id[N],scnt; void dfs2(int x,int tp) { top[x]=tp; id[x]=++scnt; if(son[x])dfs2(son[x],tp); for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to; if(to==fa[x]||to==son[x])continue; dfs2(to,to); } } //--------------------two times dfs----------------------------- ll sum[N<<2],laz[N<<2],L,R; void pushup(int x) {sum[x]=sum[x<<1]+sum[x<<1|1];} void pushdown(int x,int l,int r) { if(laz[x]) { ll mid=(l+r)>>1; laz[x<<1]+=laz[x]; laz[x<<1|1]+=laz[x]; sum[x<<1]+=(ll)(mid-l+1)*laz[x]; sum[x<<1|1]+=(ll)(r-mid)*laz[x]; laz[x]=0; } } void update(int x,int l,int r,ll v) { if(l>=L&&r<=R) { laz[x]+=v; sum[x]+=(r-l+1)*v; return ; }pushdown(x,l,r); int mid=(l+r)>>1; if(L<=mid) update(x<<1,l,mid,v); if(R>mid) update(x<<1|1,mid+1,r,v); pushup(x); } ll query(int x,int l,int r) { if(l>=L&&r<=R) return sum[x]; pushdown(x,l,r); int mid=(l+r)>>1; ll tot=0; if(L<=mid) tot+=query(x<<1,l,mid); if(R>mid) tot+=query(x<<1|1,mid+1,r); return tot; } //-----------------------seg tree------------------------ ll solve_ask(int x) { int f1=top[x]; ll tot=0; while(f1!=1) { L=id[f1],R=id[x]; tot+=query(1,1,n); x=fa[f1],f1=top[x]; } R=id[x],L=id[1]; tot+=query(1,1,n); return tot; } //-----------------------work----------------------------- void init() { n=read(),m=read(); for(int i=1;i<=n;i++) w[i]=read(); for(int i=1;i<n;i++) { int x=read(),y=read(); add(x,y),add(y,x); } dfs1(1,0); dfs2(1,1); } void work() { for(int i=1;i<=n;i++) { L=id[i],R=id[i]; update(1,1,n,w[i]); } for(int i=1;i<=m;i++) { opt=read(); if(opt==1) { int x=read(); ll a=read(); L=id[x],R=id[x]; update(1,1,n,a); } if(opt==2) { int x=read(); ll a=read(); L=id[x],R=id[x]+sz[x]-1; update(1,1,n,a); } if(opt==3) { int x=read(); printf("%lld\n",solve_ask(x)); } } } int main() { init(); work(); } |
Comments | NOTHING