题意

遥远的国度有n个城市，这些城市之间由一些路连接且这些城市构成了一颗树。这个国度有一个首都，我们可以把这个首都看做整棵树的根，但遥远的国度比较奇怪，首都是随时有可能变为另外一个城市的。遥远的国度的每个城市有一个防御值，有些时候RapiD会使得某两个城市之间的路径上的所有城市的防御值都变为某个值。RapiD想知道在某个时候，如果把首都看做整棵树的根的话，那么以某个城市为根的子树的所有城市的防御值最小是多少。

\(n \leq 100000，m \leq 100000\)

分析

重点在换根。
其实是假的换根，每次判断一下根和询问节点的关系即可。
修改使用树链剖分。
查询判断后用线段树查询。

判断关系的方法：

1. x=root，查询整棵树
2. lca(x,root)!=x，即root不在x的子树中，查询x的子树
3. lca(x,root)=x，即root在x的子树中，找到root具体在x的哪颗子树里面，查询该子树对整棵树的补集

时间复杂度\(O(N \log N+M \log^2 N)\)

代码

#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<ctime>
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<complex>
#pragma GCC optimize ("O0")
using namespace std;
template<class T> inline T read(T&x)
{
    T data=0;
    int w=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch==‘-‘)
            w=-1;
        ch=getchar();
    }
    while(isdigit(ch))
        data=10*data+ch-‘0‘,ch=getchar();
    return x=data*w;
}
typedef long long ll;
const int INF=0x7fffffff;

const int MAXN=1e5+7;
int n;

struct Edge
{
    int nx,to;
}E[MAXN<<1];
int head[MAXN],ecnt;

void addedge(int x,int y)
{
    E[++ecnt].to=y;
    E[ecnt].nx=head[x],head[x]=ecnt;
}

int a[MAXN];
int fa[MAXN],sz[MAXN],dep[MAXN],son[MAXN];
int top[MAXN],clk,dfn[MAXN];
int w[MAXN];

void dfs1(int x,int f)
{
    fa[x]=f,sz[x]=1,dep[x]=dep[f]+1;
    for(int i=head[x];i;i=E[i].nx)
    {
        int y=E[i].to;
        if(y==f)
            continue;
        dfs1(y,x);
        sz[x]+=sz[y]; // edit 1,order of +=size and dfs1
        if(sz[y]>sz[son[x]])
            son[x]=y;
    }
}

void dfs2(int x,int topf)
{
    top[x]=topf;
    dfn[x]=++clk;
    w[clk]=a[x];
    if(!son[x])
        return;
    dfs2(son[x],topf);
    for(int i=head[x];i;i=E[i].nx)
    {
        int y=E[i].to;
        if(y==fa[x]||y==son[x])
            continue;
        dfs2(y,y);
    }
}

int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}

struct SegTree
{
    int minv[MAXN<<2];
    int setv[MAXN<<2];
#define lson (now<<1)
#define rson (now<<1|1)
    void pushup(int now)
    {
        minv[now]=min(minv[lson],minv[rson]);
    }
    
    void pushdown(int now)
    {
        if(setv[now])
        {
            minv[lson]=setv[now],
            setv[lson]=setv[now];
            minv[rson]=setv[now],
            setv[rson]=setv[now];
            setv[now]=0;
        }
    }
    
    void build(int now,int l,int r)
    {
        setv[now]=0;
        if(l==r)
        {
            minv[now]=w[l];
            return;
        }
        int mid=(l+r)>>1;
        build(lson,l,mid);
        build(rson,mid+1,r);
        pushup(now);
    }
    
    void set(int now,int l,int r,int ql,int qr,int v)
    {
        if(ql<=l&&r<=qr)
        {
            minv[now]=v,
            setv[now]=v;
            return;
        }
        pushdown(now);
        int mid=(l+r)>>1;
        if(ql<=mid)
            set(lson,l,mid,ql,qr,v);
        if(qr>=mid+1)
            set(rson,mid+1,r,ql,qr,v);
        pushup(now);
    }
    
    int qmin(int now,int l,int r,int ql,int qr)
    {
        if(ql<=l&&r<=qr)
        {
            return minv[now];
        }
        pushdown(now);
        int mid=(l+r)>>1,ans=INF;
        if(ql<=mid)
            ans=min(ans,qmin(lson,l,mid,ql,qr));
        if(qr>=mid+1) // edit 1
            ans=min(ans,qmin(rson,mid+1,r,ql,qr));
        return ans;
    }
}T;

void setpath(int x,int y,int v)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        T.set(1,1,n,dfn[top[x]],dfn[x],v);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    T.set(1,1,n,dfn[x],dfn[y],v);
}

int find(int x,int r)
{
    int t;
    while(top[r]!=top[x])
    {
        t=top[r],
        r=fa[top[r]];
    }
    if(r==x)
        return t;
    else
        return son[x];
}
/*
8 999
1 2
2 3
2 4
4 8
4 5
1 6
6 7
2 3 5 11 10 6 9 12
1
3 2
2 5 6 7
3 2
*/
int main()
{
//  freopen("BZOJ3083.in","r",stdin);
//  freopen("BZOJ3083.out","w",stdout);
    int m;
    read(n);read(m);
    for(int i=1;i<n;++i)
    {
        int x,y;
        read(x);read(y);
        addedge(x,y);
        addedge(y,x);
    }
//  cerr<<"edge end"<<endl;
    for(int i=1;i<=n;++i)
        read(a[i]);
//  cerr<<"a end"<<endl;
    int r;
    read(r);
    dfs1(r,0);
    dfs2(r,r);
/*  cerr<<"dfn check"<<endl;
    for(int i=1;i<=n;++i)
        cerr<<i<<" dfn="<<dfn[i]<<endl;*/
    T.build(1,1,n);
//  cerr<<"init end"<<endl;
    while(m--)
    {
        int opt;
        read(opt);
        if(opt==1)
        {
            read(r);
        }
        else if(opt==2)
        {
//          cerr<<"modifying"<<endl;
            int x,y,v;
            read(x);read(y);read(v);
            setpath(x,y,v);
        }
        else if(opt==3)
        {
            int x,ans;
            read(x);
            if(r==x)
            {
                ans=T.minv[1];
            }
            else
            {
                int f=lca(r,x);
                if(f!=x)
                {
                    ans=T.qmin(1,1,n,dfn[x],dfn[x]+sz[x]-1);
                }
                else
                {
                    int y=find(x,r);
                    ans=INF;
                    if(1<=dfn[y]-1)
                        ans=min(ans,T.qmin(1,1,n,1,dfn[y]-1));
                    if(dfn[y]+sz[y]<=n)
                        ans=min(ans,T.qmin(1,1,n,dfn[y]+sz[y],n));
                }
            }
            printf("%d\n",ans);
/*          cerr<<"cur weight check"<<endl;
            for(int i=1;i<=n;++i)
                cerr<<i<<"  w="<<T.qmin(1,1,n,dfn[i],dfn[i])<<endl;*/
        }
    }
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

Hint

大家不要学我把dfs1和sz[x]+=sz[y]的顺序打反了，为此我调了一天。

BZOJ3083 遥远的国度

原文：https://www.cnblogs.com/autoint/p/9644611.html