我觉得这个题比起dp题反而更像构造题。。。
AGC034 E
我们考虑枚举最后到达哪个点也就是根来做。
考虑如果两个棋子成祖先关系，我们显然不会这么选，让一个下来一个上去并不优秀。
否则，我们必然会选择两个不在同一子树的点，如果设 $dist_u$ 表示 $u$ 到根的距离，那么它们的 $dist$ 分别减一。
于是可以看作把一个棋子拆成 $dist_u$ 个棋子放在它到根的路径上，每次可以选择两个不同子树的棋子消除。
我们考虑当前的根在 $u$ ，并且考虑它的所有子树，这个时候就变成了一种经典模型：一共有 $n$ 个集合，每次可以选择两个集合中分别一个数字消除，求最后最多可以消除多少对。这种模型的做法是分类讨论，我们假设这 $n$ 个集合（在这里就是 $u$ 的所有儿子子树内的棋子个数）的和为 $sum$ ，最大的集合大小为 $max$ ，那么：
$sum - max\geq max$ ，则 $ans = \lfloor \frac{sum} 2 \rfloor$ 。为什么呢？我们可以拿当前的最大的和次大的来消，最后明显只会剩下一个。。
否则，即使其他的全部来消最大的也消不完，如果是在这个模型中就是 $sum - max$ 了，但是这个题里面，我们还可以在最大的子树里面内部消，如果设最大的子树为 $v$ 也就是说
其中 $F[x]$ 表示 $x$ 为点的子树内最多可以消多少对。
显然在 $v$ 中内部消除并不影响外部的消除，所以 $k$ 可以任意选择，只要满足选择消除了 $k$ 对后仍然可以被其他的子树消完。
于是 $F$ 可以树形 dp 得出。
然后考虑什么时候这个根合法，不难发现当且仅当所有的棋子个数是 偶数 并且 $F[rt] = \frac s 2$ 时合法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "vector"
using namespace std;
#define MAXN 2006
#define P 1000000007
int n;
vector<int> G[MAXN];
int A[MAXN] , F[MAXN] , d[MAXN] , s[MAXN] , siz[MAXN] , S;
void dfs( int u , int fa ) {
if( A[u] ) s[u] = d[u] , siz[u] = 1; else siz[u] = s[u] = 0;
int mxp = 0;
for( int v : G[u] ) if( v != fa ) {
d[v] = d[u] + 1 , dfs( v , u ) , s[u] += s[v] , siz[u] += siz[v];
mxp = ( !mxp || s[v] > s[mxp] ) ? v : mxp;
}
int sum = s[u] - siz[u] * d[u] , mx = s[mxp] - siz[mxp] * d[u];
if( sum >= 2 * mx ) F[u] = sum / 2;
else
F[u] = sum - mx + min( F[mxp] , ( 2 * mx - sum ) / 2 );
}
int main() {
cin >> n;
for( int i = 1 ; i <= n ; ++ i ) scanf("%1d",&A[i]);
for( int i = 1 , u , v ; i < n ; ++ i ) {
scanf("%d%d",&u,&v);
G[u].push_back( v ) , G[v].push_back( u );
}
int res = 0x3f3f3f3f;
for( int i = 1 ; i <= n ; ++ i ) {
d[i] = 0, dfs( i , i );
if( ( ~s[i] & 1 ) && F[i] == s[i] / 2 ) res = min( res , s[i] / 2 );
}
cout << ( res == 0x3f3f3f3f ? -1 : res ) << endl;
}
|
