[tree chain dissection] 2022 Hangzhou Electric Multi school 21001 static query on tree

Static Query on Tree

Next, we will introduce the method of tree chain dissection （ That is, the second way to solve the problem ）

The main idea of the topic ：

An introverted tree , Three sets A,B,C, There are some points in each set , Find the number of specific points , Satisfaction comes from A The collection and B The set can reach this specific point , And you can arrive from this specific point C aggregate .

You can take the A Set to the root node path with A Mark , Take from B Set to the root node path with B Mark , Then the tree was hit A and B The mark is A and B Points that can be reached by the collection .（ Because it is an introverted tree , So go to the root node ）

Just judge these with A and B Whether the marked point can be reached C The node can be , The method is the same , take C Each point in the set and the point on its subtree are marked C Mark , As long as the statistics tree is marked at the same time ABC The number of marked points is enough （ In this case, you can use the segment tree to maintain the tag ）.

Segment tree records variables

• $tr[u].cnt[i]$

$tr[u].cnt[i]$ Medium $i$ There are three values ,0,1,2, Each represents being marked A Marked points , Be hit with AB Marked points , Be hit with ABC Marked points .

be $tr[u].cnt[i]$ Then it can be marked on the interval represented by the corresponding segment tree node A Number of marked points （$i=0$）, Be hit with AB Number of marked points （$i=1$）, Be hit with ABC Number of marked points （$i=2$）.

• $tr[u].flag[i]$

There are three values -1,0, 1

The initial value is equal to -1, by 0 Represents that the corresponding interval is set to 0

Lazy mark download method ：

Pass the lazy mark down A when , because A It's the first time to mark , No other conditions are required , Direct download , Make a note of cnt Variable can .

tr[u << 1].cnt[i] = tr[u].flag[i] * (mid - l + 1);
tr[u << 1 | 1].cnt[i] = tr[u].flag[i] * (r - mid); 

Pass down the lazy sign B and C when , There need to be restrictions , Pass down the lazy sign B We need to have A Mark can be marked A and B The node of , Is marked AB The number of nodes is equal to being marked A Multiply the number of nodes by the corresponding lazy tag .

tr[u << 1].cnt[i] = tr[u].flag[i] * tr[u << 1].cnt[i - 1];
tr[u << 1 | 1].cnt[i] = tr[u].flag[i] * tr[u << 1 | 1].cnt[i - 1];

Next is the board of tree chain partition , See the link below

Tree chain partition template problem

Code

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5, M = 2 * N;
const int p = 1e9 + 7;

int n, q;

struct Segment
{
    
    int cnt[3], flag[3];
}tr[N * 4];

int dep[N], fa[N], son[N], sz[N];
int cnt, nw[N], top[N], id[N];

int e[M], h[N], ne[M], idx;
void add(int a, int b)
{
    
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void pushup(int u)
{
    
    for(int i = 0; i < 3; i++)
    	tr[u].cnt[i] = tr[u << 1].cnt[i] + tr[u << 1 | 1].cnt[i];

}
void pushdown(int u, int l, int r)
{
    
    int mid = (l + r) >> 1;

    for(int i = 0; i < 3; i++)
    {
    
    	if(tr[u].flag[i] == -1)
    		continue;
    	tr[u << 1].flag[i] = tr[u].flag[i];
    	tr[u << 1 | 1].flag[i] = tr[u].flag[i];
    	if(i == 0)
    	{
    
    		tr[u << 1].cnt[i] = tr[u].flag[i] * (mid - l + 1);
    		tr[u << 1 | 1].cnt[i] = tr[u].flag[i] * (r - mid); 
    	}
    	else
    	{
    
    		tr[u << 1].cnt[i] = tr[u].flag[i] * tr[u << 1].cnt[i - 1];
    		tr[u << 1 | 1].cnt[i] = tr[u].flag[i] * tr[u << 1 | 1].cnt[i - 1];
    	}
    	tr[u].flag[i] = -1;
    }
}

void build(int u, int l, int r)
{
    
    if(l == r)
    {
    
        for(int i = 0; i < 3; i++)
        	tr[u].cnt[i] = 0;
	    for(int i = 0; i < 3; i++)
        	tr[u].flag[i] = -1;
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int l, int r, int x, int y, int d, int v)
{
    
    if(l >= x && r <= y)
    {
    
        tr[u].flag[d] = v;
        if(d == 0)
        	tr[u].cnt[0] = (r - l + 1) * v;
        else tr[u].cnt[d] = tr[u].cnt[d - 1] * v;
        return;
    }
    pushdown(u, l, r);
    int mid = (l + r) >> 1;
    if(x <= mid) modify(u << 1, l, mid, x, y, d, v);
    if(y > mid) modify(u << 1 | 1, mid + 1, r, x, y, d, v);
    pushup(u);
}

ll query(int u, int l, int r, int x, int y)
{
    
    if(l >= x && r <= y)
    	return tr[u].cnt[2] % p;
    pushdown(u, l, r);
    int mid = (l + r) >> 1;
    ll ans = 0;
    if(x <= mid) ans = query(u << 1, l, mid, x, y) % p;
    if(y > mid) ans = (ans + query(u << 1 | 1, mid + 1, r, x, y)) % p;
    return ans;
}

// Preprocessing dep[],fa[],sz[],son[]( Heavy son node )
void dfs1(int x, int f, int depth)//x :  Current node , f： father , depth： depth 
{
    
    dep[x] = depth;
    fa[x] = f;
    sz[x] = 1;
    int mxson = -1;
    for(int i = h[x]; ~i; i = ne[i])
    {
    
        int y = e[i];
        if(y == f) continue;
        dfs1(y, x, depth + 1);
        sz[x] += sz[y];
        if(sz[y] > mxson)//  Record the duplicate son number 
        {
    
            son[x] = y;
            mxson = sz[y];
        }
    }
}

//  New serial number   seek id[], nw[], top[]  new id- New node weight - Chain top 
void dfs2(int x, int topf)
{
    
    id[x] = ++cnt;
    nw[cnt] = w[x];
    top[x] = topf;
    if(!son[x]) return;// No son returns 
    dfs2(son[x], topf);
    for(int i = h[x]; ~i; i = ne[i])
    {
    
        int y = e[i];
        if(y == fa[x] || y == son[x])
            continue;
        dfs2(y, y);
    }
}

ll queryRange(int x, int y)
{
    
    ll ans = 0;
    while(top[x] != top[y])// Not on the same chain 
    {
    
        if(dep[top[x]] < dep[top[y]])
            swap(x, y);
        ans += query(1, 1, n, id[top[x]], id[x]);
        ans %= p;
        x = fa[top[x]];
    }
    if(dep[x] > dep[y])
        swap(x, y);
    ans = (ans + query(1, 1, n, id[x], id[y])) % p;
    return ans;
}

void modifyRange(int x, int y, int d, int v)
{
    
    v %= p;
    while(top[x] != top[y])
    {
    
        if(dep[top[x]] < dep[top[y]])
            swap(x, y);
        modify(1, 1, n, id[top[x]], id[x], d, v);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y])
        swap(x, y);
    modify(1, 1, n, id[x], id[y], d, v);
}
ll querySon(int x)
{
    
    return query(1, 1, n, id[x], id[x] + sz[x] - 1);  
}
void modifySon(int x, int d, int v)
{
    
    modify(1, 1, n, id[x], id[x] + sz[x] - 1, d, v);
}


int tot[3], node[4][N];

void solve()
{
    
    cin >> n >> q;
    int r = 1;
    memset(h, -1, sizeof h);
    for(int i = 2; i <= n; i++)
    {
    
    	int to;
    	cin >> to;
        add(to, i);
        add(i, to);
    }
    dfs1(r, -1, 1);
    dfs2(r, r);
    build(1, 1, n);
    while(q--)
    {
    
    	for(int i = 0; i < 3; i++)
    		cin >> tot[i];
    	for(int i = 0; i < 3; i++)
    		for(int j = 1; j <= tot[i]; j++)
    		{
    
    			cin >> node[i][j];
    			if(i != 2)
    				modifyRange(1, node[i][j], i, 1);
    			else
    				modifySon(node[i][j], i, 1);
    		}
    	cout << querySon(1) << "\n";
    	modifySon(1, 0, 0);
    	modifySon(1, 1, 0);
    	modifySon(1, 2, 0);
    }
}

int main()
{
    
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    int t;
    cin >> t;
    // t = 1;
    while(t--)
        solve();
    return 0;
}