CF1211H

Gaochenxi103_QWQ · 2025-11-27 08:03:53 · 题解

前言

由于 CF 这道题目不支持 C++ 语言的编译，所以如果有 hack 数据或我的代码有问题扣我一下。

做法

首先我们第一部分先计算出最小的最多使用颜色次数。

最大值最小，不难想到二分答案。而二分的目的是确定最多使用次数的上限。在限制了最大使用边数的情况下我们考虑用 DP 来检查当前二分的值的正确性。

因为颜色有 10^6 个，而对于一颗最多只有 3000 个结点的树而言是肯定够用的。那么假如 u 的子树内使用次数最多的颜色已经达到上限，但是我们并不用担心它是否会在后续的考虑中超出上限，因为我们根本不会再使用它。

而我们假设节点 u 的父向边颜色已知且固定为 col，而所有 u 的儿子 v，要么选择将自己的父向边颜色也设为 col；要么选择集体设为另外一种颜色。（对于根节点，我们看作它向虚拟节点连一条边即可）

而因为与 col 不同的颜色之后不会再使用，但相同的会继续参与之后的决测。所以为了尽可能满足当前的 mid。在合法情况下与 col 不同的颜色的边就尽可能用的多，这样 col 就尽可能的少之后的转移就更可能满足 mid。

那么我们定义。

如果为 dp[u]=0 说明无解。并且对于点 u 如果存在 dp[v]=0，那么说明子树 v 内无解，那么也说明子树 u 内无解。（注意在 u 为根的时候计算出 0 并不意味着无解，所以要特判一下）

那么我们怎么在知道 dp[v] 的前提下计算出最小的 dp[u]？

我们将 v 分为两个集合，一个是父向边等于 col 的 S_1，一个是父向边不等于 col 的 S_2。而我们要让不等于 col 的点的 \sum dp[v] 在不超过 mid 的前提下尽可能的大，所以这里我们可以用到 01 背包。假如跑出来 \sum_{v\in S_2}dp[v] 的值为 mx。那么 dp[u]=\sum_{v\in S_1\cup S_2}dp[v]-mx+1（如果 u 为根那么就不用加一）。

最后再特判一下 dp[u] 是否大于了 mid。如果在最小的情况下多比 mid 大，那么直接就 dp[u]=0 表示无解。

然后是第二部分的输出一种合法方案。

我们可以再用计算出来的答案跑一遍 DP。再 01 背包计算完之后，反推出一种，每个点的父向边是否和自己父亲的父向边一致的数组。计算出这个数组后再将整个树跑一遍根据数组赋值即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3030;
int T,n,mid,dp[N],faf[N],col[N];//子树u内是否有解，包含父向边且子树u内与父向边相同的最小边数，为0表示无解 
bool f[N][N];//当前决策层中，考虑到第i个f[v]已经选择了之和为j的元素是否可能  
vector<int>G[N];
vector<pair<int,int>>g;
void dfs(int u,int fa)
{
    faf[u]=fa;
    if(G[u].size()==1 && G[u][0]==fa)
    {
        dp[u]=1;
        return ;
    }
    vector<int> a(1);
    int sum=0;
    for(auto v:G[u])
    {
        if(v==fa)continue;
        dfs(v,u);
        a.push_back(dp[v]);
        sum+=dp[v];
        if(dp[v]==0)
        {
            dp[u]=0;//tang
            return ;
        }
    }
    int mx=0;
    f[0][0]=1;
    for(int i=1;i<=a.size()-1;i++)
    {
        for(int j=0;j<=mid;j++)
        {
            f[i][j]=f[i-1][j];
            if(j>=a[i])f[i][j]|=f[i-1][j-a[i]];
            if(f[i][j])mx=max(mx,j);
        }
    }
    if(u==1)
    {
        if(sum-mx>mid)dp[u]=0;
        else dp[u]=1;
        return ;
    }
    if(sum-mx+1>mid)dp[u]=0;
    else dp[u]=sum-mx+1;
}
bool check()
{
    memset(dp,0,sizeof dp);
    dfs(1,0);
    return dp[1]; 
}
bool ship[N];//与父亲的父向边关系 
void calc(int u,int fa)
{
    if(G[u].size()==1 && G[u][0]==fa)
    {
        dp[u]=1;
        return ;
    }
    vector<int> a(1);
    vector<int> b(1);
    int sum=0;
    for(auto v:G[u])
    {
        if(v==fa)continue;
        calc(v,u);
        a.push_back(dp[v]);
        b.push_back(v);
        sum+=dp[v];
    }
    int mx=0;
    f[0][0]=1;
    for(int i=1;i<=a.size()-1;i++)
    {
        for(int j=0;j<=mid;j++)
        {
            f[i][j]=f[i-1][j];
            if(j>=a[i])f[i][j]|=f[i-1][j-a[i]];
            if(f[i][j])mx=max(mx,j);
        }
    }
    dp[u]=sum-mx+1;
    int now=a.size()-1,val=mx;
//  cout<<"=="<<now<<" "<<val<<"==\n"; 
    while(now)
    {
        if(f[now-1][val])
        {
            ship[b[now]]=1;
            now--;
            continue;
        }
        if(val>=a[now] && f[now-1][val-a[now]])
        {
            ship[b[now]]=0;
            val-=a[now];
            now--;
            continue;
        }
    }
}
int cnt=0;
void init(int u,int fa)
{
    int r=-1;
    for(auto v:G[u])
    {
        if(v==fa)continue;
        if(ship[v])col[v]=col[u];
        else 
        {
            if(r==-1)r=++cnt;
            col[v]=r;
        }
        init(v,u);
    }
}
void push(int res)
{
    memset(dp,0,sizeof dp);
    calc(1,0);
//  for(int i=1;i<=n;i++)cout<<ship[i]<<"\n";
    col[1]=++cnt;
    init(1,0);
    for(auto v:g)
    {
        int a=v.first;
        int b=v.second;
//      cout<<a<<" "<<b<<"\n";
        if(faf[b]!=a)
        {
            cout<<col[a]<<" ";
        }
        else
        {
            cout<<col[b]<<" ";
        }
    }
    cout<<"\n";
    return ;
}
void solve()
{
    cin>>n;
    g.clear();
    for(int i=1;i<=n;i++)G[i].clear();
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        g.push_back({u,v});
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int l=1,r=n-1,res=n-1;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(check())
        {
            res=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    cout<<res<<"\n";
//  push(res);
    return ;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while(T--)solve();
    return 0;
}