P3979 distant country

analysis

Tree section + segment tree + classification discussion (tree section root)

Let's put the conclusion here first

• Changing the root does not affect the operation of splitting the path in the tree with the tree established from 1.
• Changing the root will affect the nature of using the subtree, because after changing the root, the node dfs order of the subtree in the tree may be discontinuous, but it can be avoided through classification discussion. See the following for details.

Let's use this topic as a model to talk about tree root dissection

There are three operations in total, and we only need to focus on the third operation.

Because the roots change, the subtrees of the same node may not be the same when the roots are different. Obviously, it is unreasonable to run a tree section every time you change the root.

That's the key we need to talk about. We can discuss it by category

Note: we only do the tree section according to point 1. Root is the capital in the title. In our tree section, we use point 1 as the root

1. If the point u to be queried is root, you can directly query the whole tree
2. If the point u to be queried is not in the path of 1 - > root, you can directly query the subtree under this node
3. It is also an important play. The point u to be queried is in the path of 1 = > root. We only need to delete the subtree of the direct son v of u from the path of U - > root. We only need to check the continuous part of the interval on both sides to get the answer.

It's mainly the third kind, which is also very good to think of

Find the direct son v of u on path U - > root

You will find that when root is the root, the place that u subtree cannot cover is v and v subtree

Let's talk about how to find your immediate son v

It's the same as looking for LCA in tree section, but it needs special judgment in the end.

If at the end, when we turn over from a chain, we directly reach u, then we can directly return to the head of the chain

If you have turned to the same chain, you can directly return to son[u].

int u = root;
while(top[u]!=top[x])
{
if(fa[top[u]]==x) return top[u];
u = fa[top[u]];
}
return son[x];

Look directly at the code below

Ac_code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10,INF = INT_MAX;
struct Node
{
    int l,r,mi,tag;
}tr[N<<2];
int h[N],e[N<<1],ne[N<<1],w[N],idx;
int sz[N],fa[N],son[N],dep[N];
int top[N],id[N],nw[N],ts;
int n,m,root;

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

void dfs1(int u,int pa,int depth)
{
    sz[u] = 1,fa[u] = pa,dep[u] = depth;
    for(int i=h[u];~i;i=ne[i])
    {
        int j = e[i];
        if(j==pa) continue;
        dfs1(j,u,depth+1);
        sz[u] += sz[j];
        if(sz[j]>sz[son[u]]) son[u] = j;
    }
}

void dfs2(int u,int tp)
{
    top[u] = tp,id[u] = ++ts,nw[ts] = w[u];
    if(!son[u]) return ;
    dfs2(son[u],tp);
    for(int i=h[u];~i;i=ne[i])
    {
        int j = e[i];
        if(j==fa[u]||j==son[u]) continue;
        dfs2(j,j);
    }
}

void pushup(int u)
{
    tr[u].mi = min(tr[u<<1].mi,tr[u<<1|1].mi);
}

void pushdown(int u)
{
    auto &root = tr[u],&left = tr[u<<1],&right = tr[u<<1|1];
    if(root.tag)
    {
        left.mi = right.mi = left.tag = right.tag = root.tag;
        root.tag = 0;
    }
}

void build(int u,int l,int r)
{
    if(l==r)
    {
        tr[u] = {l,r,nw[l]};
        return ;
    }
    tr[u] = {l,r};
    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)
{
    if(l<=tr[u].l&&tr[u].r<=r) 
    {
        tr[u].mi = tr[u].tag = x;
        return ;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if(l<=mid) modify(u<<1,l,r,x);
    if(r>mid) modify(u<<1|1,l,r,x);
    pushup(u);
}

int query(int u,int l,int r)
{
    if(l<=tr[u].l&&tr[u].r<=r) return tr[u].mi;
    int mid = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    int res = INF;
    if(l<=mid) res = min(res,query(u<<1,l,r));
    if(r>mid) res = min(res,query(u<<1|1,l,r));
    return res;
}

int find(int x)
{
    if(x==root) return 1;
    if(id[x]>=id[root]||id[x]+sz[x]-1<id[root]) return x; 
    int u = root;
    while(top[u]!=top[x])
    {
        if(fa[top[u]]==x) return top[u];
        u = fa[top[u]];
    }
    return son[x];
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++) 
    {
        int u,v;scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    for(int i=1;i<=n;i++) scanf("%d",w+i);
    scanf("%d",&root);
    dfs1(1,-1,1);
    dfs2(1,1);
    build(1,1,n);
    while(m--)
    {
        int op,x,y,z;
        scanf("%d%d",&op,&x);
        if(op==1) root = x;
        else if(op==2)
        {
            scanf("%d%d",&y,&z);
            while(top[x]!=top[y])
            {
                if(dep[top[x]]<dep[top[y]]) swap(x,y);
                modify(1,id[top[x]],id[x],z);
                x = fa[top[x]];
            }
            if(dep[x]<dep[y]) swap(x,y);
            modify(1,id[y],id[x],z);
        }
        else 
        {
            int u = find(x);
            if(u==1) printf("%d\n",query(1,1,n));
            else if(u==x) printf("%d\n",query(1,id[u],id[u]+sz[u]-1));
            else 
            {
                int res = query(1,1,id[u]-1);
                if(id[u]+sz[u]<=n) res = min(res,query(1,id[u]+sz[u],n));
                printf("%d\n",res);
            }
        }
    }
    return 0;
}