CF1830D 题解

honglan0301 · 2023-05-31 18:55:45 · 题解

题目分析

首先注意到 \text{mex} 只有三种情况，于是我们先想到贪心的思路，即让 \text{mex}=2 的情况尽可能多，这显然可以通过交替染色的方式实现，做到 n(n+1)-n-\sum [p_i=1]。

但是这样贪并不总是最优的，比如造一个在一条边两段挂分别挂很多条边的树，此时最优解是把中间两个点都染成 1，其余点染成 0。

然后可以换个角度从反面想，发现当且仅当一条路径只经过一种颜色的点时其 \text{mex} 才不为 2，这启发我们对于每种颜色的连通块分别考虑。初始情况 ans=n(n+1)，每个大小为 i、颜色为 j\in \{0,1\} 的连通块会让答案减小 \frac{i(i+1)(j+1)}{2}。

那么考虑 \text{dp}，注意到每个连通块的大小不会太大（交替染色使得答案只减小至多 2n，而一个大小为 i 的连通块会让答案减小 O(i^2)，故 i<O(\sqrt n)），于是设 f_{i,j,k} 表示点 i 的子树中，i 所在的连通块大小为 j，颜色为 k 时答案最小要减少多少。合并子树时有显然的转移：

于是做完了，下面补充一些应该是前置知识的东西。考虑时间复杂度，如上的树上背包根据 size 合并是 O(\max u\times \max i)=O(n\sqrt n) 的。证明可考虑以下几种情况：

1. 当 size_u>\sqrt n,size_v>\sqrt n 时：这样的合并至多进行 O(\frac{n}{\sqrt n})=O(\sqrt n) 次，故时间复杂度 O(n\sqrt n)。

2. 当 size_u<\sqrt n,size_v<\sqrt n 时：这等价于在每个 size<\sqrt n 的子树上做无限制的背包，容易发现找出每个 size<\sqrt n 的极大子树后时间复杂度就是 O(\sum size^2)\leq O(\max size\times \sum size)=O(n\sqrt n)。

3. 当 size_u<\sqrt n,size_v>\sqrt n 时：注意到每个点至多有一个祖先 u 会进行这样的合并，且每个点 u 至多进行一次，故时间复杂度 O(\sum size_u\times \sqrt n)=O(n\sqrt n)。

4. 当 size_u>\sqrt n,size_v<\sqrt n 时：注意到每个点至多有一个祖先 v 会进行这样的合并，且每个 v 本来就只会合并一次，故时间复杂度 O(\sum size_v\times \sqrt n)=O(n\sqrt n)。

再考虑空间复杂度，直接开满显然是 O(n\sqrt n) 的，会寄掉，于是考虑动态地开（且用完就清空释放内存），此时合并到 i 时只需保存从根到 i 的 \text{dp} 数组，并且背包大小取决于链外的节点个数（因为这条链上的 size 还没有上传），故空间 O(n)，可以通过本题。

感觉还不错，启发性在于对 \text{mex} 的贪心转化和优化 \text{dp} 的过程。

代码

/*
  author: PEKKA_l  
 */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define pb push_back
#define B 785ll
#define INF 100000000000
#define int long long

int t,n,u,v,sz[200005],g[2][805];
vector <int> e[200005],dp[200005][2];

void dfs(int x,int fat)
{
    sz[x]=1; dp[x][0].pb(INF); dp[x][1].pb(INF); dp[x][0].pb(1); dp[x][1].pb(2);
    for(auto i:e[x])
    {
        if(i==fat) continue; dfs(i,x);
        int min0=INF,min1=INF;
        for(int j=1;j<=min(B,sz[i]);j++) min0=min(min0,dp[i][0][j]),min1=min(min1,dp[i][1][j]);
        for(int j=1;j<=min(B,sz[x]);j++) g[0][j]=dp[x][0][j],g[1][j]=dp[x][1][j],dp[x][0][j]=dp[x][1][j]=INF;
        for(int j=min(B,sz[x])+1;j<=min(B,sz[x]+sz[i]);j++) dp[x][0].pb(INF),dp[x][1].pb(INF);
        for(int j=1;j<=min(B,sz[x]+sz[i]);j++)
        {
            for(int k=max(1ll,j-min(B,sz[x]));k<=min(j-1,min(B,sz[i]));k++)
            {
                dp[x][0][j]=min(dp[x][0][j],dp[i][0][k]+g[0][j-k]+j*k-k*k);
                dp[x][1][j]=min(dp[x][1][j],dp[i][1][k]+g[1][j-k]+2*j*k-2*k*k);
            }
        }
        for(int j=1;j<=min(B,sz[x]);j++)
        {
            dp[x][0][j]=min(dp[x][0][j],g[0][j]+min1); dp[x][1][j]=min(dp[x][1][j],g[1][j]+min0);
        }
        sz[x]+=sz[i]; dp[i][0].clear(); dp[i][0].shrink_to_fit(); dp[i][1].clear(); dp[i][1].shrink_to_fit();//
    }
}

signed main()
{
    cin>>t;
    while(t--)
    {
        cin>>n; for(int i=1;i<=n;i++) e[i].clear(),dp[i][0].clear(),dp[i][1].clear();
        for(int i=1;i<=n-1;i++) {cin>>u>>v; e[u].pb(v); e[v].pb(u);} dfs(1,1);
        int nans=INF; for(int i=1;i<=min(B,sz[1]);i++) nans=min(nans,min(dp[1][0][i],dp[1][1][i]));
        cout<<n*(n+1)-nans<<endl;//
    }
}