[POI2013]LUK-Triumphal arch

题目描述

The king of Byteotia, Byteasar, is returning to his country after a victorious battle.

In Byteotia, there are towns connected with only roads.

It is known that every town can be reached from every other town by a unique route, consisting of one or more (direct) roads.

(In other words, the road network forms a tree).

The king has just entered the capital.

Therein a triumphal arch, i.e., a gate a victorious king rides through, has been erected.

Byteasar, delighted by a warm welcome by his subjects, has planned a triumphal procession to visit all the towns of Byteotia, starting with the capital he is currently in.

The other towns are not ready to greet their king just yet - the constructions of the triumphal arches in those towns did not even begin!

But Byteasar‘s trusted advisor is seeing to the issue.

He desires to hire a number of construction crews.

Every crew can construct a single arch each day, in any town.

Unfortunately, no one knows the order in which the king will visit the towns.

The only thing that is clear is that every day the king will travel from the city he is currently in to a neighboring one.

The king may visit any town an arbitrary number of times (but as he is not vain, one arch in each town will suffice).

Byteasar‘s advisor has to pay each crew the same flat fee, regardless of how many arches this crew builds.

Thus, while he needs to ensure that every town has an arch when it is visited by the king, he wants to hire as few crews as possible.

Help him out by writing a program that will determine the minimum number of crews that allow a timely delivery of the arches.

给一颗树，1号节点已经被染黑，其余是白的，两个人轮流操作，一开始B在1号节点，A选择k个点染黑，然后B走一步，如果B能走到A没染的节点则B胜，否则当A染完全部的点时，A胜。求能让A获胜的最小的k

输入输出格式

The first line of the standard input contains a single integer (), the number of towns in Byteotia.

The towns are numbered from 1 to , where the number 1 corresponds to the capital.

The road network is described in lines that then follow.

Each of those lines contains two integers, (), separated by a single space, indicating that towns and are directly connected with a two way road.

In tests worth 50% of the total points, an additional condition holds.

The first and only line of the standard output is to hold a single integer, the minimum number of crews that Byteasar‘s advisor needs to hire.

输入输出样例

7
1 2
1 3
2 5
2 6
7 2
4 1

3

说明

给一颗树，1号节点已经被染黑，其余是白的，两个人轮流操作，一开始B在1号节点，A选择k个点染黑，然后B走一步，如果B能走到A没染的节点则B胜，否则当A染完全部的点时，A胜。求能让A获胜的最小的k

先二分答案，再dfs判断，f[i]表示i这颗子树还需多少次染色（不包括自己）

#include<bits/stdc++.h>
using namespace std;

const int maxn = 3e5+10;

int n,size,head[maxn],f[maxn],maxd;

struct edge{
    int v,nex;
}e[maxn<<1];

void adde(int u,int v) {
    e[size].v=v;
    e[size].nex=head[u];
    head[u]=size++;
}

void dfs(int u,int fa,int mid) {
    int sum=0;
    for(int i=head[u];~i;i=e[i].nex) {
        int v=e[i].v;
        if(v==fa) continue;
        dfs(v,u,mid);
        sum+=f[v]+1;
    }
    f[u]=max(0,sum-mid);
}


int main() {
    memset(head,-1,sizeof(head));
    scanf("%d",&n);
    if(n==1) {puts("0");return 0;}
    int l=1,r=n;
    for(int i=1;i<n;i++) {
        int u,v;scanf("%d%d",&u,&v);
        adde(u,v);adde(v,u);
    }
    int ans=0;
    while(l<=r) {
        int mid=(l+r)>>1;
        dfs(1,-1,mid);
        if(f[1]==0) {
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    printf("%d",ans);
    return 0;
}

View Code