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

Lyrella · 2025-11-10 21:51:16 · 题解

题解

首先可以图论建模，没想到可以退役了。然后题意就相当于是对于每个起点终点，都会走出若干路径，但是这些路径肯定都会过一些固定点（比如起点终点）。现在要对每个 z 计算有多少合法点对 (x,y)，合法指的是过 x,y 的任意路径都与以 z 为端点的路径有一个交点。因为交点是一个定点，相当于我两个点的路径一定经过这个点，所以他是一个割点。于是我们可以想到对图建圆方树，然后在每个圆点上考虑贡献。因为 x,y,z 不在同一个子树中且三点等价，于是就记录每个交点对其他点的贡献即可。

代码

inline void dfs1(int u, int fa){
    sz[u] = u <= n; ll res = 0;
    for(int i = hd[u], v; ~ i; i = e[i].nxt)if((v = e[i].to) != fa)
        dfs1(v, u), res += sz[u] * sz[v], sz[u] += sz[v];
    if(u > n)return; f[0] += res; f[u] += sz[u] * (n + 1 - sz[u]);
    for(int i = hd[u], v; ~ i; i = e[i].nxt)if((v = e[i].to) != fa)
        f[v] -= sz[v] * (n + 1 - sz[v]);
}
inline void dfs2(int u, int fa){for(int i = hd[u], v; ~ i; i = e[i].nxt)if((v = e[i].to) != fa)f[v] += f[u], dfs2(v, u);}

signed main(){
    tot = n = rd(), lim = rd(); b[0] = 1; memset(hd, - 1, sizeof hd);
    for(int i = 1; i <= n; ++i)
        g[i / 3].push_back(i), g[i].push_back(i / 3),
        b[i] = b[i / 3] * 3;
    for(int i = 1; i <= lim; ++i)if(i % 3 > 0){
        int j = (i % 3) * b[i / 3] + i / 3;
        if(j <= n)g[i].push_back(j), g[j].push_back(i);
    }
    tar(0); dfs1(0, - 1); dfs2(0, - 1);
    for(int i = 0; i <= n; ++i)wt(f[i] << 1), pc('\n');
    return 0;
}