XJ - 梦色之乡 | Jason Fan.

题意简述

给你一个 $n$ 个点的树， $m$ 次询问，每次询问删除 $x,y$ 两子树后树的重心。

$n,m \le 100000$

题解

一个很烂的正解，~~别看了~~

官方题解

sol

std.cpp:

#include<cstdio>
#include<algorithm>
#include<ctime>
using namespace std;
const int inf=0x3f3f3f3f;
struct node{int size,id,iid;};
struct edge{int last,en,next;} e[200010];
int n,x,y,son[100010],size[100010],dfn[100010],dep[100010];
int st[100010][18],tot,cnt,cs[100010],q,u,v,ccs[100010];
int f[100010][18],val[100010],g[100010][18],leave[100010],ans,w,sum;
void add(int x,int y)
{
    e[++tot].en=y;
    e[tot].next=e[x].last;
    e[x].last=tot;
}
inline int read()
{
    int s=0;
    char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s; 
}
void dfs(int x,int fa)
{
    f[x][0]=fa;dep[x]=dep[fa]+1;size[x]=1;
    dfn[x]=++cnt;son[x]=0;
    for(int i=e[x].last;i;i=e[i].next) 
        if (e[i].en!=fa)
        {
            dfs(e[i].en,x);
            if (size[son[x]]<size[e[i].en])
            {
                ccs[x]=cs[x];
                cs[x]=son[x];
                son[x]=e[i].en;
            }
            else if (size[cs[x]]<size[e[i].en]) 
            {
                ccs[x]=cs[x];
                cs[x]=e[i].en;
            }
            else if (size[ccs[x]]<size[e[i].en]) ccs[x]=e[i].en;
            size[x]+=size[e[i].en];
        }
    val[x]=size[son[x]]-size[cs[x]];
    if (!cs[x]) val[x]=0x3f3f3f3f; 
    st[x][0]=val[x];g[x][0]=son[x];
    leave[x]=++tot;
}
int lca(int x,int y)
{
    if (dep[x]<dep[y]) swap(x,y);
    for (int i=17;i>=0;i--)
        if (dep[f[x][i]]>=dep[y]) x=f[x][i];
    if (x==y) return x;
    for (int i=17;i>=0;i--)
        if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
int calc(int z,int x)
{
    if (dfn[u]>=dfn[x]&&leave[u]<=leave[x]) z-=size[u];
    if (dfn[v]>=dfn[x]&&leave[v]<=leave[x]) z-=size[v];
    return z;
}
bool getpos(int x,int y)
{
    if (dfn[x]>=dfn[y]&&leave[x]<=leave[y]) return true;
    return false;
}
void sort3(node &a,node &b,node &c)
{
    if (a.size<b.size) swap(a,b);
    if (a.size<c.size) swap(a,c);
    if (b.size<c.size) swap(b,c);
}
void sort3(int &a,int &b,int &c)
{
    if (a<b) swap(a,b);
    if (a<c) swap(a,c);
    if (b<c) swap(b,c);
}
bool get(int x)
{
    int a,b,c;
    a=calc(size[son[x]],son[x]);
    b=calc(size[cs[x]],cs[x]);
    c=calc(size[ccs[x]],ccs[x]);
    sort3(a,b,c);
    if (a<=sum/2) return true;
    return false;
}
void getans(int x)
{
    for (int i=17;i>=0;i--)
        if (f[x][i]&&get(f[x][i])) x=f[x][i];
    int y=0;
    node a,b,c;
    a=(node){calc(size[son[x]],son[x]),getpos(u,son[x])?u:getpos(v,son[x])?v:0,son[x]};
    if (son[x]==u||son[x]==v) a.size=-inf;
    b=(node){calc(size[cs[x]],cs[x]),getpos(u,cs[x])?u:getpos(v,cs[x])?v:0,cs[x]};
    if (son[x]==u||son[x]==v) a.size=-inf;
    c=(node){calc(size[ccs[x]],ccs[x]),getpos(u,ccs[x])?u:getpos(v,ccs[x])?v:0,ccs[x]};
    if (son[x]==u||son[x]==v) a.size=-inf;
    sort3(a,b,c);
    if (sum-a.size<=sum/2&&a.size!=-inf) y=a.iid;
    if (x>y) swap(x,y);
    if (x) printf("%d %d\n",x,y);
    else printf("%d\n",y);
}
void solve(int x)
{
    bool bj=getpos(w,x);
    if (!bj)
    {
        for (int i=17;i>=0;i--)
            if (g[x][i]) x=g[x][i];
        getans(x);
        return;
     } 
    else
    {    
        for (int i=17;i>=0;i--)
        {
            int y=g[x][i];
            if (!y||!getpos(w,y)&&y!=w||getpos(y,u)||getpos(y,v)) continue;
            if (calc(st[x][i],y)>=0) x=y;
        }
    }
    node a,b,c;
    if (x==u||x==v) x=f[x][0];
    a=(node){calc(size[son[x]],son[x]),getpos(u,son[x])?u:getpos(v,son[x])?v:0,son[x]};
    if (son[x]==u||son[x]==v||!son[x]) a.size=-inf;
    b=(node){calc(size[cs[x]],cs[x]),getpos(u,cs[x])?u:getpos(v,cs[x])?v:0,cs[x]};
    if (cs[x]==u||cs[x]==v||!cs[x]) b.size=-inf;
    c=(node){calc(size[ccs[x]],ccs[x]),getpos(u,ccs[x])?u:getpos(v,ccs[x])?v:0,ccs[x]};
    if (ccs[x]==u||ccs[x]==v||!ccs[x]) c.size=-inf;
    sort3(a,b,c);
    if (a.size==-inf)
    {
        getans(x);
        return;
    }
    if (getpos(a.iid,w)) w=a.id;
    solve(a.iid);
}
int main()
{
    freopen("dream.in","r",stdin);
    freopen("dream.out","w",stdout);
    n=read();q=read(); 
    for (int i=1;i<n;i++)
        x=read(),y=read(),add(x,y),add(y,x),st[i][0]=inf;
    st[0][0]=inf;    
    dfs(1,0);
    for (int j=1;j<=17;j++)
        for (int i=1;i<=n;i++)
        {
            f[i][j]=f[f[i][j-1]][j-1],g[i][j]=g[g[i][j-1]][j-1];
            st[i][j]=min(st[i][j-1],st[g[i][j-1]][j-1]);
        }
    dfn[0]=leave[0]=size[0]=0;
    while (q--)
    {
        
        scanf("%d%d",&u,&v);ans=0;
        if (u==1||v==1)
        {
            printf("0\n");
            continue;
        }
        w=lca(u,v);
        if (u==w) v=0;
        else if (v==w) u=0;
        sum=n-size[u]-size[v];
        solve(1);
    }
    return 0;
}

整点阳间的：

记点 $u$ 的子树大小 $siz_u$ ，若 $S$ 为总点数，若 $siz_u \le \frac{S}{2}$ 那么父亲方向上的子树大小为 $S-siz_u\ge \frac{S}{2}$ ， $u$ 跳到其父亲更优，那我们要找的点满足 $siz_{u}>\frac{S}{2}$ 。我们在重心的子树中找一个点 $u$ ，跳到的第一个满足要求的点就是重心。

再考虑如何起始点 $u$ ，结论是：我们令 $u$ 为该树 dfn 序的最中间那个点即可。
证明：一个子树对应 dfn 序上一段区间，考虑中心 $x$ 必然满足 $siz_x>\frac{S}{2}$ 对应 dfn 序上一段长度大于等于总长一半的区间，必然包含中间点，即中间点 $u$ 必然在 $x$ 的子树内。

删子树即在 dfn 序上删除一段区间，删除子树后的 $siz$ 也容易维护。

需要注意的是当有两个重心的时候：

如图， $u,v$ 为重心， $u$ 是 $v$ 的父亲， $u,v$ 两边子树大小都为 $\frac{S}{2}$ （ $S$ 必然是偶数）。此时如果我们把起始点定为 dfn 排序为 $\frac{S}{2}$ 的点可能会跳不到 $v$ 点（当图中红圈中的点在 dfn 序中排 $1\sim \frac{S}{2}$ ) ，此时选排名 $\frac{S}{2}+1$ 的点就可以了（必然在蓝圈里）。

CODE

#include <bits/stdc++.h>
template <typename Tp>
inline void read(Tp &x) {
    x = 0; bool fg = 0; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') fg ^= 1; ch = getchar();}
    while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (Tp)(ch ^ 48), ch = getchar();
    if (fg) x = -x;
}
template <typename Tp, typename... Args>
void read(Tp &t, Args &...args) { read(t); read(args...); }
using namespace std;
typedef long long ll;
const int N = 100010;
const int M = 21;
int head[N], nxt[N << 1], pnt[N << 1], E;
int siz[N], dfL[N], dfR[N], dfn[N], tim;
int fa[M][N];
int n, m;
void adde(int u, int v) {
    E++; pnt[E] = v; nxt[E] = head[u]; head[u] = E;
}
void dfs(int u, int f, int d) {
    dfL[u] = ++tim; siz[u] = 1; fa[0][u] = f;
    dfn[tim] = u;
    for (int i = 1; i < M && fa[i - 1][u]; ++i) fa[i][u] = fa[i - 1][fa[i - 1][u]];
    for (int i = head[u]; i; i = nxt[i]) {
        int v = pnt[i];
        if (v == f) continue;
        dfs(v, u, d + 1);
        siz[u] += siz[v];
    }
    dfR[u] = tim;
}
bool fa_son(int u, int v) {
    return dfL[u] <= dfL[v] && dfR[v] <= dfR[u];
}
int x1, x2;
int getsize(int u) {
    return siz[u] - fa_son(u, x1) * siz[x1] - fa_son(u, x2) * siz[x2] +
           (fa_son(u, x1) && fa_son(u, x2) && (fa_son(x1, x2) || fa_son(x2, x1))) * min(siz[x1], siz[x2]);
}
int main() {
    read(n, m);
    for (int i = 1; i < n; ++i) {
        int u, v; read(u, v);
        adde(u, v); adde(v, u);
    }
    dfs(1, 0, 0);
    // for (int i = 1; i <= n; ++i) {
    //     printf("%d%c", dfn[i], " \n"[i == n]);
    // }
    for (int t = 1; t <= m; ++t) {
        read(x1, x2);
        if (x1 == 1 || x2 == 1) {
            puts("0");
            continue;
        }
        int x = -1, tot, mid;
        if (fa_son(x1, x2) || fa_son(x2, x1)) {
            int L = min(dfL[x1], dfL[x2]), R = max(dfR[x1], dfR[x2]);
            tot = n - (R - L + 1); mid = tot / 2 + 1;
            if (mid < L) x = dfn[mid];
            else x = dfn[R + mid - L + 1];
        } else {
            int L1 = dfL[x1], R1 = dfR[x1], L2 = dfL[x2], R2 = dfR[x2];
            if (L2 < L1) swap(L1, L2), swap(R1, R2);
            tot = n - (R1 - L1 + 1) - (R2 - L2 + 1); mid = tot / 2 + 1;
            if (mid < L1) x = dfn[mid];
            else if (mid <= L1 - 1 + L2 - R1 - 1) x = dfn[R1 + mid - L1 + 1];
            else x = dfn[R2 + mid - (L1 + L2 - R1 - 1) + 1];
        }
        // cerr << "tot = " << tot << " x = " << x << endl;
        int a1 = x, a2 = 0;
        if (getsize(x) < (tot + 1) / 2) {
            for (int i = M - 1 ; i >= 0; --i) {
                if (fa[i][x] && getsize(fa[i][x]) < (tot + 1) / 2) x = fa[i][x];  
            }
            a1 = fa[0][x];
        }
        if (getsize(a1) * 2 == tot) a2 = fa[0][a1];
        if (a2) printf("%d %d\n", min(a1, a2), max(a1, a2));
        else printf("%d\n", a1);
    }
    return 0;
}
/*
5 2
1 2
1 3
2 4
2 5
4 5
5 3
*/