题目：
有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个
操作，分为三种：
操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。
树链剖分，单点修改，查询最大值和总和。
|
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 |
#include<iostream> #include<cstdio> #define ll long long using namespace std; int n,m,tot,lable,Next[210000],head[210000],tree[210000],fa[210000],dep[210000],size[210000]; int son[210000],tid[210000],number[210000],top[210000]; ll f[210000],a[880000],L[880000],R[880000],lazy[880000]; bool visit[410000]; void add(int x,int y) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; } void dfs(int x,int depth,int father) { visit[x]=true;fa[x]=father;dep[x]=depth;size[x]=1;son[x]=0; int maxsize=0; for (int i=head[x];i;i=Next[i]) if (!visit[tree[i]]) { dfs(tree[i],depth+1,x); size[x]+=size[tree[i]]; if (size[tree[i]]>maxsize) { maxsize=size[tree[i]]; son[x]=tree[i]; } } } void dfs1(int x,int ancestor) { visit[x]=true;tid[x]=++lable;number[lable]=x;top[x]=ancestor; if (son[x]!=0) dfs1(son[x],ancestor); for (int i=head[x];i;i=Next[i]) if (!visit[tree[i]]) dfs1(tree[i],tree[i]); } void dfs2(int x) { visit[x]=true;L[x]=tid[x];R[x]=tid[x]; for (int i=head[x];i;i=Next[i]) if (!visit[tree[i]]) { dfs2(tree[i]); if (R[tree[i]]>R[x]) R[x]=R[tree[i]]; } } void up(int id) { a[id]=a[id*2]+a[id*2+1]; } void down(int id,ll x) { if (lazy[id]!=0) { a[id*2]+=lazy[id]*((x+1)/2); a[id*2+1]+=lazy[id]*(x/2); lazy[id*2]+=lazy[id]; lazy[id*2+1]+=lazy[id]; lazy[id]=0; } } void swap(int &x,int &y) { int t=x;x=y;y=t; } void build(int id,int l,int r) { lazy[id]=0; if (l==r) { a[id]=f[number[l]]; return; } int mid=(l+r)/2; build(id*2,l,mid); build(id*2+1,mid+1,r); up(id); } ll query(int x,int y,int id,int l,int r) { if (l>y||r<x) return 0; down(id,r-l+1); if (x<=l&&r<=y) return a[id]; int mid=(l+r)/2; return query(x,y,id*2,l,mid)+query(x,y,id*2+1,mid+1,r); } ll Query(int x,int y) { ll ans=0; while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); ans+=query(tid[top[x]],tid[x],1,1,n); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); ans+=query(tid[x],tid[y],1,1,n); return ans; } void change(int x,int y,int id,int l,int r,ll d) { if (l>y||r<x) return; down(id,r-l+1); if (x<=l&&r<=y) { a[id]+=d*(r-l+1); lazy[id]+=d; return; } int mid=(l+r)/2; change(x,y,id*2,l,mid,d); change(x,y,id*2+1,mid+1,r,d); up(id); } int main() { scanf("%d%d",&n,&m); tot=lable=0; for (int i=1;i<=n;i++) scanf("%lld",&f[i]); for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y);add(y,x); } for (int i=1;i<=n;i++) visit[i]=false; dfs(1,1,0); for (int i=1;i<=n;i++) visit[i]=false; dfs1(1,1); for (int i=1;i<=n;i++) visit[i]=false; dfs2(1); build(1,1,n); for (int i=1;i<=m;i++) { int q; scanf("%d",&q); if (q==1) { int x;ll y; scanf("%d%lld",&x,&y); change(tid[x],tid[x],1,1,n,y); } if (q==2) { int x;ll y; scanf("%d%lld",&x,&y); change(L[x],R[x],1,1,n,y); } if (q==3) { int x; scanf("%d",&x); printf("%lld\n",Query(1,x)); } } return 0; } |
