rockdu
题目描述
Everyone knew it would only be a matter of time. So what?
Faced for years on, a peril becomes the every-day reality.
It loses its meaning...
Today the letter of the Bitotian char Bittard to the Byteotian king Byteasar was released to the public.
Bitotia requested annexation of the whole Byteotia on pain of using the Bit Polarizing Magnet (BPM).
If used, the BPM would make each and every road in Byteotia unidirectional.
The enemy knows only too well that this could be a fatal blow to the minimalist Byteotian infrastructure - there is a unique way between each pair of towns.
How badly can the BPM damage the Byteotian infrastructure?
Determine the minimum and the maximum number of such pairs of towns that it will still be possible to travel from one of them to the other while observing the new roads orientation.
给定一颗树，请给树边改成有向边，求连通的点对个数的最大最小值。点对连通，要么a能到达b，要么b能到达a。(n<=250000)
输入输出格式
输入格式：
The first line of the standard input gives a single integer (
), the number of towns in Byteotia.
The lines that follow describe these roads.
Each such line holds two integers, and
(
), which indicate that there is a direct road (still bidirectional at the moment) linking the towns no.
and
.
In tests worth 60% of the total points, the additional constraint holds;moreover, in some of those, worth 30% of the total points, it even holds that
.
输出格式：
Two integers should be printed to the first and only line of the standard output.
The first number should be the minimum and the second - the maximum number of pairs of towns which could remain connected (though in one direction only) after the roads are polarized.
输入输出样例
说明
给定一颗树，请给树边改成有向边，求连通的点对个数的最大最小值。点对连通，要么a能到达b，要么b能到达a。(n<=250000)
第一眼就觉得这个题有结论。
最少的点对不难发现就是相邻层之间边一个朝根一个朝叶子的连，可达点就是n-1个。
那么最多呢？
错误做法：枚举一个点当根，然后dfs一遍移动出所有点当根的答案。
实际上我们发现这个图完全可以是一个DAG，显然收益会更大。
比如如下的图：
这时候稍加观察，我们发现最多点对的定向方案中，每一条从入度为0的点延伸的链一定"过"重心(原谅我语文不好，但它真的是过重心那个意思)。那么我们就把重心找出来，这时候它下面的每一颗子树要么全部指向重心(根)，要么全部指向叶子，并且在一棵子树内这两种方案的贡献是相同的。那么我们只需要最大化自上而下的贡献，也就是将指向重心的子树size和和指向叶子的子树size和变得最小(总和不变，乘积最大)。那么是一个完全背包问题。
然后250000的完全背包？……
看完题解发现有骚操作，因为所有物品(子树)总容量为n，那我们分情况讨论：
如果重心度数大于sqrt(n)，那么子树size的种类一定不超过sqrt(n)种
如果重心度数小于sqrt(n)也可以过。那就一遍多重背包即可(我卡了个常)
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<cmath>
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 5e5 + 5;
struct edge {
int v, next;
}e[maxn << 1];
int head[maxn], cnt;
void adde(const int &u, const int &v) {
e[++cnt] = (edge) {v, head[u]};
head[u] = cnt;
}
int n, u, v, siz[maxn], mx, son[maxn], G, tot[maxn];
int itm[maxn], ans;long long els;
int Gans(int u, int f, int d, int & G) {
int v, ret = 0; siz[u] = 1;
for(register int i = head[u]; i; i = e[i].next) {
v = e[i].v;
if(v == f) continue;
ret += Gans(v, u, d + 1, G);
siz[u] += siz[v];
if(siz[v] > son[u]) son[u] = siz[v];
}
son[u] = max(son[u], n - siz[u]);
if(son[u] <= n / 2) G = u;
ret += siz[u] - 1;
return ret;
}
void dfs(int u, int f) {
int v;siz[u] = 1;
for(register int i = head[u]; i; i = e[i].next) {
v = e[i].v;
if(v == f) continue;
dfs(v, u), siz[u] += siz[v];
}
}
bitset<maxn> dp;
int main() {
scanf("%d", &n);
For(i, 1, n - 1) scanf("%d%d", &u, &v), adde(u, v), adde(v, u);
printf("%d ", n - 1);
Gans(1, 0, 0, G), dp[0] = 1;
dfs(G, 0);
for(register int i = 1; i <= n; ++i) els += siz[i] - 1;
for(register int i = head[G]; i; i = e[i].next) {
v = e[i].v;
if(siz[G] > siz[v]) itm[++itm[0]] = siz[v];
else itm[++itm[0]] = n - siz[u] - 1;
}
int NSQT = (int)sqrt(n);
if(itm[0] <= NSQT)
for(register int i = 1; i <= itm[0]; ++i)
dp |= dp << (itm[i]);
if(itm[0] > NSQT) {
for(register int i = 1; i <= itm[0]; ++i)
++tot[itm[i]];
itm[0] = 0;
for(register int i = 1; i <= n; ++i)
if(tot[i]) itm[++itm[0]] = i, tot[itm[0]] = tot[i];
for(register int i = 1, p = 1; i <= itm[0]; ++i, p = 1) {
for(p = 1; p <= tot[itm[0]]; p <<= 1) dp |= dp << (itm[i] * p);
dp |= dp << (itm[i] * (tot[itm[0]] - p));
}
}
for(register int i = n / 2; i >= 0; --i)
if(dp[i]) {ans = i; break;}
printf("%lld", 1ll * els + 1ll * ans * (n - ans - 1));
return 0;
}
没有帐号? 立即注册