题目传送门(BZOJ)
>原文链接<

题解 :

我们把两问分开看

第一问 :

考虑以点$x$为顶点的线要多少根.

由于有一条线是从父亲来的, 并且还可以继续向下给它的一个儿子, 所以就是其他儿子两两配对需要的线条数

即$\lceil\frac{\deg[x]-2}{2}\rceil$,也就是$\lfloor\frac{\deg[x]-1}{2}\rfloor$

其中根节点需要特判, 它没有从父亲来的线, 也就是先在答案上加一, 来表示这条线是继承下来的线.

$1+\sum\limits_{i=1}^{n}\lfloor\frac{\deg[i]-1}{2}\rfloor$

第二问 :

第二问有很鲜明的二分标志 : 最长最短.

我们先二分一个答案$mid$, 然后考虑如何验证 :

$f[i]=f[to]+1$, 我们先把$i$的儿子的$f$拿过来排个序,

此时我们再二分一下, 假设$i$从父亲那继承来的点要给点$now$接下去,

那么删掉$now$后,其他点贪心的两两配对长度不能超过$mid$

这样我们在二分出来的可行的前提下贪心的使$f[i]$尽可能的小, 因为这样会有利于以后的答案.

直接拿那个尽可能小的答案来更新$f$即可

根节点同样需要特判, 配对删最大的即可

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)char buf[100000], *p1, *p2; const int N = 11000;inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc(); return x;}#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)struct Edge { int to; Edge *next;}*h[N], e[N<<1];inline void addEdge(int u, int v) { static int _; Edge *tmp = &e[++_]; tmp->to = v; tmp->next = h[u]; h[u] = tmp;}int deg[N], f[N], g[N], n, mid;bool flag;inline bool check(int x) { for(int i = 1, j = *g; i < j; i ++, j -- ) { if(i == x) ++ i; if(j == x) -- j; if(g[i]+g[j] > mid) return 0; } return 1;}void dfs(int p, int fa) { rev(i, p) if(i->to != fa) dfs(i->to, p); *g = 0; rev(i, p) if(i->to != fa) g[++*g] = f[i->to]+1; if(p == 1) { sort(g+1, *g+g+1); flag &= check((*g&1)?*g:0); return ; } if(!(*g&1)) g[++*g] = 0; sort(g+1, *g+g+1); int l = 1, r = *g+1; while(l < r) { int now = (l+r) >> 1; if(g[now]+1 <= mid && check(now)) r = now; else l = now+1; } flag &= (l!=*g+1); f[p] = g[l];}int main() { n = rd(); for(int i = 2; i <= n; i ++ ) { int u = rd(), v = rd(); deg[u] ++, deg[v] ++ ; addEdge(u, v), addEdge(v, u); } int ans = 1; for(int i = 1; i <= n; i ++ ) ans += (deg[i]-1)>>1; printf("%d ", ans); int l = 1, r = n; while(l < r) { mid = (l+r) >> 1; flag = 1; dfs(1, 0); if(flag) r = mid; else l = mid+1; } printf("%d\n", l);}