题解：P11220 【MX-S4-T4】「yyOI R2」youyou 的三进制数

· · 题解

P11220 【MX-S4-T4】「yyOI R2」youyou 的三进制数 题解

前言

给出一种实现起来较为容易的树上差分（换根 dp）的线性做法。

正文

首先我们观察题目给的四个性质，容易发现前两个性质是互逆的，后两个性质也是互逆的。

那我们考虑建图，将能够满足题目性质的一对数进行连边，连出来的就是无向边。

直接暴力建图是 O(n) 的。

我们接下来考虑一个三元组 (x,y,z) 什么时候是“好的”。

显然可以观察到的是，对于一个满足条件的 b 序列，它一定对应着图上一条从 x 到 y 的简单路径。而对于 c 序列，它对应着一条从 z 开始的简单路径。

考虑最后一个条件：同时，对于上述任意的 b，均有恰好一对 (i, j)，满足 1 \le i \le |b|，1 \le j \le |c|，使得 b_i = c_j。

对应到图上，这个条件就相当于需要存在一条从 z 开始的简单路径，它根所有从 x 到 y 的简单路径有且仅有一个交点。

引理：对于一条确定的路径 c，它所有路径 b 的交点必须是唯一的。

证明： 反证法，假设一条路径 c 根两个不同的 b 存在两个不同的交点 i 和 j，不妨假设路径 c 由 z \to i \to j \to ed 构成，b_1 为 x \to i \to y，b_2 为 x \to j \to y，那么必然存在路径 b_3 为 x \to i \to j \to y，它根路径 c 存在两个交点，与题意矛盾，于是假设不成立。

根据引理，所有 b 必须有同一交点，也就是说，这个交点是 x 到 y 的路径上的必经之点。这启示我们建出圆方树，那么这些必经之点就是树上 x 到 y 路径上的所有圆点（包括起点和终点）。接下来我们称这些点为关键点。

为了方便，我们定义一个点是路径上的点当且仅当存在一条从 x 到 y 的路径经过这个点。

那么对于一对 (x,y)，能对 z 产生贡献当且仅当：

对应到圆方树上，z 要么是 x 到 y 路径上的圆点，要么是以其中任一圆点为根，这个圆点上的不包括 x 和 y 所在的子树的任意一个点。

画个图直观感受一下（比较粗糙，见谅）。

对于一对 (x,y)，图中用三角形框起来的子树（包括树根的圆点）都能得到贡献。

我们不妨以 0 号节点为根，进行 dfs。

显然在方点上没有贡献，我们只需要考虑圆点。

令 siz_x 表示圆方树上以 x 为根子树的圆点数量。比如我们当前 dfs 到子树 t，我们类似换根 dp 的思路，把 t 当作根，那么对于节点 t 的两棵子树 x 和 y，它会对其他所有除了这两棵子树内的点造成 2\times siz_x\times siz_y 的贡献（包括 t 子树外的点）。也就是对整棵树加上这个贡献，再对这两棵子树减去这个贡献，这个可以树上差分。

具体对于子树外的点的情况，由于对整棵树加贡献再对子树外的所有点减贡献等价于直接对整棵子树加贡献，所以这个树上差分是容易实现的。

于是这题便做完了，总时间复杂度 O(n)。

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll read(){
    ll X = 0,r = 1;
    char ch = getchar();
    while(!isdigit(ch) && ch != '-') ch = getchar();
    if(ch == '-') r = -1,ch = getchar();
    while(isdigit(ch)) X = X*10+ch-'0',ch = getchar();
    return X*r;
}
const int N = 6e5+10;
int n,w,cnt;
vector<int> G[N],E[N];
int bas[N];
int dfn[N],low[N],stk[N],top,num;
void tarjan(int x,int ft){
    stk[++top] = x;
    low[x] = dfn[x] = ++num;
    for(int y : G[x]){
        if(y == ft) continue;
        if(!dfn[y]){
            tarjan(y,x);
            low[x] = min(low[x],low[y]);
            if(low[y] >= dfn[x]){
                cnt++;
                int z;
                do{
                    z = stk[top--];
                    E[cnt].push_back(z);
                    E[z].push_back(cnt);
                }while(z != y);
                E[cnt].push_back(x);
                E[x].push_back(cnt);
            }
        }else low[x] = min(low[x],dfn[y]);
    }
}
ll siz[N],f[N];
void dfs(int x,int ft){
    siz[x] = x <= n;
    ll sum = 0;
    for(int y : E[x]){
        if(y == ft) continue;
        dfs(y,x);
        sum += siz[y]*siz[x];
        siz[x] += siz[y];
    }
    if(x <= n){
        for(int y : E[x]){
            if(y == ft) continue;
            f[y] -= (n+1-siz[y])*siz[y];
        }
        f[0] += sum;
        f[x] += siz[x]*(n+1-siz[x]);
    }
}
void dfs0(int x,int ft){
    for(int y : E[x]){
        if(y == ft) continue;
        f[y] += f[x];
        dfs0(y,x);
    }
}
int main(){
    n = read(); w = read();
    auto add_edge = [&](int x,int y){
        G[x].push_back(y);
        G[y].push_back(x);
    };
    for(int i=1;i<=n;i++) add_edge(i/3,i);
    bas[0] = 1;
    for(int i=1;i<=n;i++) bas[i] = bas[i/3]*3;
    for(int i=1;i<=w;i++){
        if(i % 3 == 0) continue;
        int x = i/3,y = i%3;
        x = bas[x]*y+x;
        if(x <= n) add_edge(x,i);
    }
    cnt = n;
    tarjan(0,0);
    dfs(0,0); dfs0(0,0);
    for(int i=0;i<=n;i++) cout << f[i]*2 << "\n";
    return 0;
}