题解：P3563 [POI 2013] POL-Polarization

· · 题解

题目给出了一棵树，然后要求我们把所有无向边替换成有向边，再求出可到达点对的最少和最大数量。

首先，最小值的答案是显而易见的。因为不管所有的构造方式，令一条边从 u 通向 v，那么经过该边的答案就是能到达 u 的点数乘以能到达 v 的点数。

所以既然是相乘，两个乘数的差值肯定是越大越好，所以不妨让所有点都指向某个节点，这时答案为 n-1。

那么反过来，求最大值的思想就是使乘数的差值尽可能小，即我们选出来的关键点，满足通向它的点与被它通向的点的差值最小。（这里的“通向”仅代表方向，而非直接连通）

所以那个关键点就是重心，因为只有这样我们才可以更自由的调配所有与这个点直接连通的点与关键点的方向。

我们以重心 \text{rt} 为根重新建树，然后对于新根的每一个子节点，我们都计算出以他为根的子树大小 \text{sz}，并看作一个重量为 \text{sz} 的物品，最后要尽可能装满容量为 \frac n2 的背包。

我们维护 dp_{i,j} 表示使用前 i 个物品是否能到达 j，若能到达，则 dp_{i,j}=1，否则为 0。

若最后装了 v，则答案为：

\sum_{\text{son}\in \text{rt}} sz_\text{son}+v\cdot (n-v-1)

但这样的时间复杂度为 O(N^2)，使用二进制拆分可优化到 O(N\sqrt N)。

这里简单证明一下，若无二进制拆分，那么有 n-1 个 \text{sz}=1 的物品时，就会被卡成 O(N^2)。

当二进制拆分后，为了使二进制拆分尽量不发挥作用，我们构造序列 1,2,3\cdots k 作为物品，且 \sum_{i=1}^ki=n-1，即 \frac{(1+k)\cdot k}{2}=n-1，那么 k 可到达 \sqrt{N} 级别，也就是拆分后依旧有 \sqrt{N} 个物品。

因此总时间复杂度为 n 乘上物品数，即最大的 k，所以时间复杂度为 O(N\sqrt N)。

注意到 dp_i\in \{0,1\}，因此我们可以用 bitset 维护 dp 数组，因此可以再乘一个 \frac{1}{64} 的常数，可以通过本题。

code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2.5e5 + 10;
int n,rt,ans,pos,sz[N],mx[N],cnt[N];
vector<int> e[N];
bitset<N> dp;
void dfs(int u,int fa){
    mx[u] = 0;
    sz[u] = 1;
    for(int v : e[u]){
        if(v == fa) continue;
        dfs(v,u);
        sz[u] += sz[v];
        mx[u] = max(mx[u],sz[v]);
    }
    mx[u] = max(mx[u],n - sz[u]);
    if(!rt || mx[u] < mx[rt]) rt = u;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    dp[0] = 1;
    for(int i = 1;i < n;++i){
        int u,v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    dfs(rt,0);
    ans = -sz[rt];
    for(int i = 1;i <= n;++i) ans += sz[i];//子树内贡献
    for(int v : e[rt]) ++cnt[sz[v]];
    for(int i = 1;i <= n / 2;++i){
        while(cnt[i] > 2){
            cnt[i] -= 2;
            ++cnt[i << 1];
        }
    }
    for(int i = 1;i <= n;++i){
        while(cnt[i]--) dp |= (dp << i);
    }
    for(int i = (n >> 1);i >= 0;--i){
        if(dp[i]){
            pos = i;
            break;
        }
    }
    cout << n - 1 << ' ' << ans + pos * (n - pos - 1);
    return 0;
}