「雅礼集训 2018-04-02」Problem C

发表于

Alice 和 Bob 在玩游戏。

有一棵 NN 个节点的树， Alice 和 Bob 轮流操作，Alice 先手。 一开始树上所有节点都没有颜色，Alice 每次会选一个没有被染色的节点并把这个节点染成红色(不能不选)，Bob 每次会选一个没有被染色的节点并把这个节点染成蓝色(不能不选)。当有人操作不了时，游戏就终止了。

Alice 的最终得分为红色连通块的个数，Bob 的最终的分为蓝色连通块的个数。设 Alice 的得分为 KAK_A ，Bob 的得分为 KBK_B，Alice 想让 KA−KBK_A-K_B 尽可能大，Bob 则想让 KA−KBK_A-K_B 尽可能小，假设两人都采取最优策略操作，那么 KA−KBK_A-K_B 会是多少。

这里指的连通块为一个点集 SS，满足集合内点的颜色相同，且每个点都能只经过 SS 内的点走到 SS 内的其他点，而且如果将任意 u(u⊈S)u(u\nsubseteq S) 加入 SS ，那么上述性质将不能被满足。

Constraints

$ n \leq 10^5 $

Solution

显然，KAK_{A} 等于红色点数减去两端都为红色的边的数量，KBK_{B} 同理。两种颜色点数是确定的，问题转化为求两边同色的边数之差。对于一条边，将两个端点的点权 +1+1 ，若被 Alice 选择则将答案减去点权，否则加上点权。贪心可得，Alice 和 Bob 都会选择点权最小的结点。贪心计算出来的数字即为 ans⋅2ans\cdot 2 。

Code

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
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=1e5+5;
int n,ans,u,v,deg[N];
int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int main()
{
    n=read();ans=(n&1)*2;
    for(int i=1;i<n;i++)
    {
        u=read();v=read();
        deg[u]++;deg[v]++;
    }
    sort(deg+1,deg+n+1);
    for(int i=1;i<=n;i++)
    {
        if(i&1)ans-=deg[i];
        else ans+=deg[i];
    }
    printf("%d",ans/2);
    return 0;
}