[POI2013]Polaryzacja

题目大意：

给定一棵\(n(n\le250000)\)个点的树，可以对每条边定向成一个有向图，这张有向图的可达点对数为树上有路径从\(u\)到达\(v\)的点对\((u,v)\)个数。求最小可达点对数和最大可达点对数。

思路：

显然最小可达点对数是\(n-1\)。一种构造就是根结点全是入边，与根结点相邻的点全是出边……以此类推。最后相邻的点对会被统计一次，其余的均不会被统计。

对于最大可达点对数，一定存在一种方案，使得树根是树的任意一个重心时，将所有子树分成两部分，一部分有\(k\)个点，另一部分有\((n-k-1)\)个点，答案就是\(\max\{(n-k-1)k+\sum(dep(i)-1)\}\)。

具体证明略。

我们可以用一个背包来求出所有可能的\(k\)，但是时间复杂度是\(\mathcal O(n^2)\)，就算使用bitset优化也无济于事。

因此我们可以将所有子树\(size\)按照大小分开转移。\(>\sqrt n\)的不超过\(\sqrt n\)个，可以直接暴力转移；\(\le\sqrt n\)的按照大小分组一起转移，具体转移时可以按照二进制拆分。

时间复杂度\(\mathcal O(\frac{n\sqrt n}\omega)\)。

源代码：

#include<cmath>
#include<cstdio>
#include<cctype>
#include<vector>
#include<bitset>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
typedef long long int64;
const int N=250001,M=501;
std::vector<int> e[N];
inline void add_edge(const int &u,const int &v) {
e[u].push_back(v);
e[v].push_back(u);
}
int64 sum;
int n,m,size[N],max[N],cen,cnt[M];
std::bitset<N> f;
void dfs(const int &x,const int &par) {
size[x]=1;
for(unsigned i=0;i<e[x].size();i++) {
const int &y=e[x][i];
if(y==par) continue;
dfs(y,x);
size[x]+=size[y];
max[x]=std::max(max[x],size[y]);
}
max[x]=std::max(max[x],n-size[x]);
if(max[x]<max[cen]) cen=x;
}
void dfs(const int &x,const int &par,const int &dep) {
sum+=dep-1;
for(unsigned i=0;i<e[x].size();i++) {
const int &y=e[x][i];
if(y==par) continue;
dfs(y,x,dep+1);
}
}
int main() {
max[0]=n=getint(),m=sqrt(n);
for(register int i=1;i<n;i++) {
add_edge(getint(),getint());
}
dfs(1,0);
dfs(cen,0,1);
f[0]=true;
for(register unsigned i=0;i<e[cen].size();i++) {
const int &y=e[cen][i];
if(size[y]<=m) {
cnt[size[y]]++;
} else {
f|=f<<size[y];
}
}
for(register int i=1;i<=m;i++) {
for(register int j=1;j<=cnt[i];j<<=1) {
f|=f<<(i*j);
cnt[i]-=j;
}
if(cnt[i]) f|=f<<(i*cnt[i]);
}
int k;
int64 ans=0;
for(k=0;k<=n;k++) {
if(f[k]) ans=std::max(ans,sum+(int64)k*(n-k-1));
}
printf("%d %lld\n",n-1,ans);
return 0;
}