P2590 [ZJOI2008]树的统计
题目链接：https://www.luogu.org/problem/P2590
注意这题有负权。 （不然你就只能跑10分！）
1 #include <stdio.h> 2 #include <algorithm> 3 #include <iostream> 4 #include <stdbool.h> 5 #include <stdlib.h> 6 #include <string> 7 #include <string.h> 8 #include <stack> 9 #include <queue> 10 #include <set> 11 #include <map> 12 #include <math.h> 13 14 #define INF 0x3f3f3f3f 15 #define LL long long 16 using namespace std; 17 18 const int maxn = 300100; 19 20 struct Edge{ 21 int to,next; 22 }edge[maxn*4]; 23 24 int head[maxn],tot; 25 26 void add_edge(int u,int v){ 27 edge[++tot] = Edge{v,head[u]}; 28 head[u] = tot; 29 } 30 31 int v[maxn]; 32 int fa[maxn]; 33 int siz[maxn]; 34 int dep[maxn]; 35 int son[maxn]; 36 37 void dfs1(int u,int f){ 38 fa[u] = f; 39 dep[u] = dep[f] + 1; 40 siz[u] = 1; 41 int maxsize = -1; 42 for (int i=head[u];~i;i=edge[i].next){ 43 int v = edge[i].to; 44 if (v == f){ 45 continue; 46 } 47 dfs1(v,u); 48 siz[u] += siz[v]; 49 if (siz[v] > maxsize){ 50 maxsize = siz[v]; 51 son[u] = v; 52 } 53 } 54 } 55 56 57 int tim; 58 int dfn[maxn]; 59 int top[maxn]; 60 int w[maxn]; 61 62 void dfs2(int u,int t){ 63 dfn[u] = ++tim; 64 top[u] = t; 65 w[tim] = v[u]; 66 if (!son[u]){ 67 return ; 68 } 69 dfs2(son[u],t); 70 for (int i=head[u];~i;i=edge[i].next){ 71 int v = edge[i].to; 72 if (v == fa[u] || v == son[u]){ 73 continue; 74 } 75 dfs2(v,v); 76 } 77 } 78 79 80 struct segment_tree{ 81 int l,r; 82 LL val; 83 LL maxval; 84 int lazy; 85 }tree[maxn*4]; 86 87 void pushup(int nod){ 88 tree[nod].val = (tree[nod<<1].val + tree[(nod<<1)+1].val); 89 tree[nod].maxval = max(tree[nod<<1].maxval,tree[(nod<<1)+1].maxval); 90 } 91 92 void build (int l,int r,int nod){ 93 tree[nod].l = l; 94 tree[nod].r = r; 95 if (l == r){ 96 tree[nod].lazy = 0; 97 tree[nod].val = w[l]; 98 tree[nod].maxval = w[l]; 99 return ; 100 } 101 int mid = (l + r) >> 1; 102 build(l,mid,nod<<1); 103 build(mid+1,r,(nod<<1)+1); 104 pushup(nod); 105 } 106 107 void modify(int k,int value,int nod=1){ 108 if (tree[nod].l == k && tree[nod].r == k){ 109 tree[nod].val = tree[nod].maxval = value; 110 return ; 111 } 112 int mid = (tree[nod].l + tree[nod].r) >> 1; 113 if (k <= mid){ 114 modify(k,value,nod<<1); 115 } 116 else 117 modify(k,value,(nod<<1)+1); 118 pushup(nod); 119 } 120 121 122 LL query(int x,int y,int k){ 123 int l = tree[k].l,r = tree[k].r; 124 if (x <= l && y >= r){ 125 return tree[k].val; 126 } 127 int mid = (l + r) >> 1; 128 LL sum = 0; 129 if (x <= mid){ 130 sum += query(x,y,k<<1); 131 } 132 if (y > mid){ 133 sum += query(x,y,(k<<1)+1); 134 } 135 return sum; 136 } 137 138 LL query2(int x,int y,int k){ 139 int l = tree[k].l,r = tree[k].r; 140 if (x <= l && y >= r){ 141 return tree[k].maxval; 142 } 143 int mid = (l + r) >> 1; 144 LL sum = -INF; 145 if (x <= mid){ 146 sum = max(sum,query2(x,y,k<<1)); 147 } 148 if (y > mid){ 149 sum = max(query2(x,y,(k<<1)+1),sum); 150 } 151 return sum; 152 } 153 154 LL query_max(int x,int y){ 155 LL ret = -INF; 156 while (top[x] != top[y]){ 157 if (dep[top[x]] < dep[top[y]]) 158 swap(x,y); 159 ret = max(ret,query2(dfn[top[x]],dfn[x],1)); 160 x = fa[top[x]]; 161 } 162 if (dep[x] > dep[y]) 163 swap(x,y); 164 ret = max(ret,query2(dfn[x],dfn[y],1)); 165 return ret; 166 } 167 168 LL query_sum(int x,int y){ 169 LL ret = 0; 170 while (top[x] != top[y]){ 171 if (dep[top[x]] < dep[top[y]]) 172 swap(x,y); 173 ret += query(dfn[top[x]],dfn[x],1); 174 x = fa[top[x]]; 175 } 176 if (dep[x] > dep[y]) 177 swap(x,y); 178 ret += query(dfn[x],dfn[y],1); 179 return ret; 180 } 181 182 int main(){ 183 int n; 184 scanf("%d",&n); 185 memset(head,-1, sizeof(head)); 186 for (int i=1;i<=n-1;i++){ 187 int x,y; 188 scanf("%d%d",&x,&y); 189 add_edge(x,y); 190 add_edge(y,x); 191 } 192 for (int i=1;i<=n;i++){ 193 scanf("%d",&v[i]); 194 } 195 dfs1(1,1); 196 dfs2(1,1); 197 build(1,n,1); 198 int T; 199 scanf("%d",&T); 200 while (T--){ 201 char s[10]; 202 int x,y,z; 203 scanf("%s",s); 204 if (strcmp(s,"CHANGE") == 0){ 205 scanf("%d%d",&x,&z); 206 modify(dfn[x],z); 207 } 208 else if (strcmp(s,"QMAX") == 0) { 209 scanf("%d%d",&x,&y); 210 printf("%lld\n",query_max(x,y)); 211 } 212 else if (strcmp(s,"QSUM") == 0){ 213 scanf("%d%d",&x,&y); 214 printf("%lld\n",query_sum(x,y)); 215 } 216 } 217 return 0; 218 }
