XF 换根

· · 算法·理论

XF 换根是由 sLMxf 和 General0826 共同研发的算法，其优势有：

前置知识：三度化

三度化是一种将多叉树转为二叉树的方式。怎么转呢？先考虑一棵树中一个节点 x 和它的子节点 son 们：

对于所有的儿子 son_i，定义辅助节点 v_i，连接 x\to v_1、v_1\to v_2……，以及 v_i\to son_i。

这样子所有的点的度数控制在了 3 之内，极其的优秀。

在三度化中也可以设置边权： 将本来 x\to son_i 的边权 w_i 挂在 v_i\to son_i 即可。

三度化代码实现

void init(int x,int fa)
{
    int cnt=0,rt=x;
    for(int v:G[x])
        if(v!=fa)
        {
            scc[++id]=x; // 建立的 vi 本质上是 x, 需要记录所属真实节点
            add(id,rt);add(rt,id);
            add(id,v);add(v,id);
            rt=id;
        }
    for(int v:G[x]) if(v!=fa) init(v,x);
}

XF 换根

以 P3478 [POI 2008] STA-Station 为例题。

考虑一种朴素做法：

定义 dp_{i,fa} 表示当 i 的父亲为 fa 时，以 i 为根作为子树的答案，辅助数组 siz_{i,fa} 表示同上情况下子树 i 的大小。

有转移方程：

dp_{i,fa}=1+\sum_{\substack{v\in nbr_i\\v\ne fa}}(dp_{v,i}+siz_{v,i})\\ siz_{i,fa}=1+\sum_{\substack{v\in nbr_i\\v\ne fa}}siz_{v,i}

（其中，nbr_i 表示树上 i 的相邻节点）

以上的做法显然，此处不谈。

不难发现，以上的做法会多次计算 dp_{i,fa} 和 siz_{i,fa}，不妨考虑对其记忆化搜索。

这里推荐使用链式前向星进行 XF 换根。对于任意的 (i,fa) 其实就是对应一条有向边，直接使用链式前向星存储的编号进行 DP 即可。

void dfs(int x,int fa,int w)
{
    if(w&&vis[w]) return ;
    vis[w]=dp[w]=siz[w]=1;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==fa) continue;
        dfs(v,x,i);
        dp[w]+=dp[i]+siz[i];
        siz[w]+=siz[i];
    }
    return ;
}

以 i 为根的答案就是 dfs(i,0,0)。

时间复杂度

考虑任意的一个点 x，假设度数为 d_x，则会进入这个点 d_x 次，每一次转移 (d_x-1) 次，时间复杂度 O(d_x(d_x-1))。

总的时间复杂度 O\left(\sum\limits_{i=1}^n d_i^2\right)。

XF 换根的优化

注意到时间复杂度只与度数有关，但是是和度数的平方和有关。

我们考虑修改原树，进行优化使得所有点的度数控制在一个小范围内。

而三度化恰好满足了这个要求。所以使用三度化即可解决这个问题。

同一个 scc 中，只有深度最浅的点表示原节点，在其余虚拟节点只执行合并子节点。

时间复杂度 O(n)，常数比较大。

XF 换根的实现较为简单，这里随便放一个 例题 的 AC 代码：

:::success[XF 换根]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+6;
int head[N],tot=0,id,n,vit[N],scc[N];
vector<int>son;
struct node{
    int v,nxt;
}e[N*2];
vector<int>G[N];
void add(int u,int v)
{
    tot++;
    e[tot].nxt=head[u];
    e[tot].v=v;
    head[u]=tot;
}
int dp[N*2],siz[N*2],vis[N*2];
void make_vit(int x,int fa)
{
    int cnt=0,rt=x;
    for(int v:G[x])
        if(v!=fa)
        {
            scc[++id]=x;
            add(id,rt);add(rt,id);
            add(id,v);add(v,id);
            rt=id;
        }
    for(int v:G[x]) if(v!=fa) make_vit(v,x);
}
void dfs(int x,int fa,int w=0)
{
    if(vis[w]) return ;
    if(w)vis[w]=1;
    siz[w]=vit[x];
    dp[w]=0;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==fa) continue;
        dfs(v,x,i);
        dp[w]^=dp[i]; // Union
        siz[w]+=siz[i];
    }
    if(scc[fa]!=scc[x]) dp[w]^=siz[w]*scc[x]; // Add
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int u,v;
    cin>>n;
    for(int i=1;i<=n;i++) vit[i]=1,scc[i]=i;
    for(int i=1;i<n;i++)
    {
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    id=n;
    make_vit(1,0);
    for(int i=1;i<=n;i++)
    {
        scc[0]=0;
        dfs(i,0);
        cout<<dp[0]<<'\n';
    }
    return 0;
}

:::

如果你觉得实现有些复杂，其实是我写的太难看了。

例题解剖

P3478 [POI 2008] STA-Station

不是我哪里没讲清楚了。

P6419 [COCI 2014/2015 #1] Kamp

本题本来还是有点难度的，但在 XF 换根面前也不过是模板题罢了。

定义 dp_x 表示以 x 为根的子树答案，不难发现：

dp_x=\sum_{v\in son_x}[dp_v>0](dp_v+2w_{x\to v})

最后对答案减去一个最长链。

使用 XF 换根，优化之 O(n) 即可。

P13248 [GCJ 2014 #1A] Full Binary Tree

简单题。

P6584 重拳出击

咋了不就是 XF 换根板子吗。

枚举小 Z 最后跑到哪里去就可以了。