Occupation
Miceren wants to occupy some cities here. Each city has a value . (Notice that the value of a city may be negative. Nevertheless, Miceren wants to occupied this city.)
As some usual stories, someone named Cloud wants to "steal" some cities from Miceren.
At the beginning, Miceren and Cloud don't occupy any city.
In the following days, one of three events may happen
Miceren will walk from the a-th city to the b-th city and all cities visited in this trip will belong to Miceren. ()
Cloud will steal the x-th city. If Miceren occupied the x-th city before, Miceren will lost the control of this city. ()
Miceren will occupy the subtree rooted at x.()
As Miceren's friend, you must tell Miceren the total value of all cities which belong to Miceren after each day.
Input The first line contains a single integer , indicating the number of test cases.
Each test case begin with one integer , indicating the number of cities in HY.
The next line contains integer , indicating the value of each city.
The next lines contain the details of the roads. Each line contains two integers meaning that there is a road between cities and .
The next line contains one integer .
The next lines contain the details of event. If the format is "1 a b", it means the first event happened where Miceren walks from a-th city to b-th city. If the format is “2 x”, it means the second event happened where Cloud "steal"s the x-th city. Otherwise the format is “3 x” and the third event happened where Micron occupied the subtree rooted at x.
is about 100.
The ratio of test cases with is less than 5%.
Output For each test queries, print the answer.
1
10
1 2 3 4 5 6 7 8 9 10
1 2
1 3
2 4
2 5
5 9
5 10
3 6
3 7
3 8
6
1 10 4
1 9 7
2 5
3 4
2 4
1 6 10
Sample Output
21
41
36
36
32
43
思路：线段树+树链剖分
首先树链剖分出dfs序，然后按照dfs序建树，特别的，维护一个active记录已经被占领的有效值，最后总的有效值即为答案。
对于操作一，采用树上操作即可，即每次从x跳到top[x]直到x与y在同一条链上。 对于操作二，直接update。 对于操作三，每个子树的dfn是连续的，所以可以直接update。
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<queue>
#include<math.h>
#include<string>
#include<map>
#include<functional>
using namespace std;
#define length 100005
int d[length];//深度
int f[length];//父亲
int Size[length];//以X为根的子树的大小
int son[length];//表示X的儿子
int top[length];//表示x所在的重链的顶端
int head[length];//,head[i] 存储以 i 为起点的第1条边的下标
int dfn = 0, Nid[length], Oid[length];//记录访问序
struct edge
{
int to;
//int w;
int nex;
}e[length * 2];
struct point
{
int val;
int tag;
int active;
}segtree[length * 4];
int A[length];
int T, N, Q;
void pushup(int rt)
{
segtree[rt].val = segtree[rt * 2].val + segtree[rt * 2 + 1].val;
segtree[rt].active = segtree[rt * 2].active + segtree[rt * 2 + 1].active;
}
void build(int l, int r, int rt)
{
segtree[rt].tag = 0;
segtree[rt].active = 0;
if (l == r)
{
segtree[rt].val = A[Oid[l]];//刚开始写成了Nid，出了几次错误，Nid为i映射到dfn，Oid为dfn映射到i。
return;
}
int m = (l + r) / 2;
build(l, m, rt * 2);
build(m + 1, r, rt * 2 + 1);
pushup(rt);
}
void pushdown(int rt, int ln, int rn)
{
if (segtree[rt].tag)
{
segtree[rt * 2].tag = segtree[rt].tag;
segtree[rt * 2 + 1].tag = segtree[rt].tag;
segtree[rt * 2].active = segtree[rt * 2].val;
segtree[rt * 2 + 1].active = segtree[rt * 2 + 1].val;
segtree[rt].tag = 0;//特别注意：记得把标记清零。若标记不清零，此次残留的标记将会影响下次的更新。
}
}
//区间更新--求M占领的总价值
void update(int L, int R, int C, int l, int r, int rt)
{
if (L <= l&&r <= R)
{
segtree[rt].tag = C;
if (segtree[rt].tag)
{
segtree[rt].active = segtree[rt].val;
}
else
{
segtree[rt].active = 0;
}
return;
}
int m = (l + r) / 2;
pushdown(rt, m - l + 1, r - m);
if (L <= m)update(L, R, C, l, m, rt * 2);
if (R > m)update(L, R, C, m + 1, r, rt * 2 + 1);
pushup(rt);
}
int Query(int L, int R, int l, int r, int rt)
{
if (L <= l&&R >= r)
{
return segtree[rt].active;
}
if (L > r || R < l)
{
return 0;
}
int m = (l + r) / 2;
pushdown(rt, m - l + 1, r - m);
return Query(L, R, l, m, rt * 2) + Query(L, R, m + 1, r, rt * 2 + 1);
}
//加边
int cnt = 1;
void add_edge(int u, int v)
{
e[cnt].to = v;
e[cnt].nex = head[u];
head[u] = cnt++;
}
//求出d f son size
void dfs1(int x, int fath)
{
Size[x] = 1;
d[x] = d[fath] + 1;
son[x] = 0;
f[x] = fath;
for (int i = head[x]; i; i = e[i].nex)
{
int to = e[i].to;
if (to == fath)
{
continue;
}
dfs1(to, x);
Size[x] += Size[to];
if (Size[son[x]] < Size[to])
{
son[x] = to;
}
}
}
//求出top
void dfs2(int x, int topx)
{
top[x] = topx;
Nid[x] = ++dfn;
Oid[dfn] = x;
if (son[x] != 0)dfs2(son[x], topx);
for (int i = head[x]; i; i = e[i].nex)
{
if (e[i].to != f[x] && e[i].to != son[x])
{
dfs2(e[i].to, e[i].to);//开启一个新的重链
}
}
}//如果对x为根的整个子树操作，对应区间为[Nid[x],Nidp[x]+Size[x]-1]
//LCA
int lca(int x, int y)
{
while (top[x] != top[y])
{
if (d[top[x]] < d[top[y]])
{
swap(x, y);
}
x = f[top[x]];
}
return d[x] < d[y] ? x : y;
}
//树上操作
void chain(int x, int y)
{
while (top[x] != top[y])
{
if (d[top[x]] < d[top[y]])
{
swap(x, y);
}
update(Nid[top[x]], Nid[x], 1, 1, N, 1);
//做具体处理top[x]到x这一段
x = f[top[x]];
}
if (d[x]>d[y])
{
swap(x, y);
}
update(Nid[x], Nid[y], 1, 1, N, 1);
//具体处理x到y这一段，比如修改这一段节点的值
}
//初始化
void init_m()
{
memset(d, 0, sizeof(d));
memset(f, 0, sizeof(f));
memset(Size, 0, sizeof(Size));
memset(son, 0, sizeof(son));
memset(top, 0, sizeof(top));
memset(head, 0, sizeof(head));
memset(Nid, 0, sizeof(Nid));
memset(Oid, 0, sizeof(Oid));
cnt = 1;
dfn = 0;
}
int main(void)
{
scanf("%d", &T);
while (T--)
{
scanf("%d", &N);
init_m();
for (int i = 1; i <= N; i++)
{
scanf("%d", &A[i]);
}
for (int i = 1; i <= N - 1; i++)
{
int u, v;
scanf("%d %d", &u, &v);
add_edge(u, v);
add_edge(v, u);
}
dfs1(1, 0);
dfs2(1, 1);
build(1, N, 1);
scanf("%d", &Q);
for (int i = 1; i <= Q; i++)
{
int op;
scanf("%d", &op);
if (op == 1)
{
int a, b;
scanf("%d %d", &a, &b);
chain(a,b);
}
if (op == 2)
{
int x;
scanf("%d", &x);
update(Nid[x], Nid[x], 0, 1, N, 1);
}
if (op == 3)
{
int x;
scanf("%d", &x);
update(Nid[x], Nid[x] + Size[x] - 1, 1, 1, N, 1);
}
printf("%d\n", segtree[1].active);
}
}
system("pause");
return 0;
}
京公网安备 11010502036488号