题解：P12038 [USTCPC 2025] 送温暖

· · 题解

广告：USTCPC2025 题解汇总（部分）。

注意到重心的最大的子树的 size 小于 \frac{n}{2}，这个性质使得把重心拆出来形成的多个子树划分成两个集合，每个集合的 size 的和不超过 \frac{2}{3}n。事实上这个东西可以卡满，考虑让重心当根然后分 3 个一样大的子树。

合并两个集合可以枚举一个集合里的所有带着根的答案去在另一个集合里二分。

大体做法就是这样，不需要详细解释，我重点说一些细节，事实上这个做法在理论上是题面说的暴力，而且貌似还有时间复杂度更优的做法，这个东西直接写是过不了的，现在说几个卡常的方法。

首先一定要保证 chk 的复杂度不要假掉，这里一定要只带一个 n，判断连通可以保留集合内所有边然后在当前判的集合里数多少边是在当前判的集合有多少条边，然后用 popcount 算点数，点数减边数就是连通块个数，连通块个数是 1 的时候合法，这样可以避开并查集的大常数。

然后经过我的测试，对 set 进行 lower_bound 的时间复杂度疑似是错的，就算是对的也是大常数，所以应该先放到 vector 里面进二分。

划分集合的过程未必要真正的去完美的划分，事实上我记得有这么一个题好像正解是随机化，大概就是说把 n 个数划分成两个集合使得两个集合和的差绝对值最小，大概就是直接贪心的把当前的数放到小的集合，然后随机打乱多做几次，可以认为这么做是对的。

具体的直接看程序吧，这次没有 42 队的赛时代码，是我自己写的，42 队做出了帮我卡常的贡献。

为防止因火车头导致无法过审，这里省略了缺省源，只放核心程序。

#define debug if(1.0*(clock()-t0)/CLOCKS_PER_SEC>=0.6)cout<<"-1",exit(0)
vint a[40];unsigned b[40],m,seed=time(0);unsigned t0=clock();
#define R() (seed^=(seed^=(seed<<11)>>13)<<17)
struct tree{set<unsigned>s,id;vint c;unsigned rt,n,f[40],res;unsigned mp[40],e[40][40],$[40][2],d;
    void ins(vint _){for(cit&i:_)id.emplace(i),++n;}
    void init(){int i=0;for(cit&j:id)mp[j]=++i;res=0;
        for(cit&u:id)for(cit&v:a[u]){cit x=mp[u],y=mp[v];debug;
        if(!y)continue;e[x][y]=e[y][x]=1;}d=0;
        for(i=1;i<=n;++i)for(int j=1;j<i;++j)if(e[i][j])++d,$[d][0]=i,$[d][1]=j;
        c+=(unsigned)0;for(cit&j:id)c+=b[j];}
    il unsigned fd(cit x){return f[x]==x?x:f[x]=fd(f[x]);}
    il unsigned calc(cit _){int sum=0;for(int i=1;i<=n;++i)if(_&(1<<i))sum+=c[i],sum>=m?sum-=m:0;return sum;}
    void chk(cit _){int cnt=0;
        for(int i=1;i<=d;++i)if((_&(1<<$[i][0]))&&(_&(1<<$[i][1])))++cnt;
        cnt=__builtin_popcount(_)-cnt;if(cnt>1)return;
        cit t=calc(_);res=max(res,t);if(_&(1<<rt))s.emplace(t);
    }void ans(){rt=mp[rt];for(int i=0;i<(1<<n);++i)chk(i<<1);}
}t1,t2;unsigned rt,dp[40],s[40],f[40];unsigned n;
void dfs(cit u){s[u]=1;for(cit&v:a[u])if(v^f[u])dfs(v),s[u]+=s[v],dp[u]=max(s[v],dp[u]);dp[u]=max(n-s[u],dp[u]);}
void gf(cit u){s[u]=1;for(cit&v:a[u])if(v^f[u])f[v]=u,gf(v),s[u]+=s[v];}
il vint val(cit u){vint _;_+=u;for(cit&v:a[u])_+=val(v);return _;}
void init(){rd(n),rd(m);int mn=40,s1=0,s2=0,b1=0,b2=0;
    for(int i=2;i<=n;++i)a[f[i]=rd()]+=i,a[i]+=f[i];dfs(1);
    for(int i=1;i<=n;++i)mn>dp[i]?mn=dp[i],rt=i:0,rd(b[i]);
    cle(f);gf(rt);for(int i=1;i<=n;++i)a[i]=vint();vint _,a1,a2;
    for(int i=1;i<=n;++i)a[f[i]]+=i;for(cit&v:a[rt])if(v)a[n+1]+=v;
    for(cit&v:a[rt])s1<s2?(s1+=s[v],a1+=v):(s2+=s[v],a2+=v);
    vint ans1=a1,ans2=a2;for(int i=1;i<=16;++i){
        a1=vint(),a2=vint(),b1=b2=0;
        for(int j=a[rt].SZ-1;j;--j)swap(a[rt][j],a[rt][R()%j]);
        for(cit&v:a[rt])b1<b2?(b1+=s[v],a1+=v):(b2+=s[v],a2+=v);
        if(max(s1,s2)>max(b1,b2))b1=s1,b2=s2,ans1=a1,ans2=a2;}
    for(cit&v:ans1)t1.ins(val(v));for(cit&v:ans2)t2.ins(val(v));
    _+=rt,t1.ins(_),t1.init(),_=vint(),_+=n+1,t2.ins(_),t2.init();
}void solve(){init();t1.rt=rt,t2.rt=n+1;t1.ans(),t2.ans();int ans=0;
    if(t1.s.SZ>t2.s.SZ)swap(t1.s,t2.s);vint tt;for(cit&x:t2.s)tt+=x;
    for(cit&x:t1.s){auto it=lower_bound(tt.begin(),tt.end(),m-x);if(it==tt.begin())continue;--it;ans=max(x+*it,ans);}
    cout<<max(ans,max(t1.res,t2.res));
}signed main(){open;int t=1;//cin>>t;
    while(t--)solve();}