洛谷P4572 [JSOI2013] 哈利波特与死亡圣器
题目描述
伏地魔的黑暗势力控制了魔法部与霍格沃茨魔法学校之后，哈利与罗恩、赫敏不得不逃亡在外，隐形遁迹。为了完成校长邓布利多的遗命，一直在暗中寻机销毁伏地魔魂器的哈利，意外地获悉如果他们能够拥有传说中的三件死亡圣器，伏地魔将必死无疑。
在凤凰社成员的帮助下，哈利一行人重新掌控了霍格沃茨。然而此举激怒了伏地魔，他很快率领大批食死徒和黑暗生物向霍格沃茨进军。麦格教授紧急疏散了霍格沃茨的学生，并开始了守卫霍格沃茨的战斗。
霍格沃茨魔法学校的主要建筑共有 n处，我们编号为 1 到n，这些建筑间由魔法道路连接，整体呈树状分布，即任意两个建筑间有且仅有一条路径相连（路径可以是一条或多条道路组成）。霍格沃茨历经多年风雨，每个建筑自身有许多保护魔法，比如“石墩触动咒”、“降敌陷阱咒”、“统统加护咒”等，只需有人前往施用咒语即能保卫建筑。
现在，伏地魔大军已经到达 1 号建筑——学校大门，凤凰社成员也已经在大门迎战，并且已经启用了大门的保护魔法。然而伏地魔大军势力壮大，保护魔法只能延缓大军的进攻锋芒，他们仍能用一个小时攻克一个建筑，随后整个大军便随机前往与之相邻的另一个建筑（兵贵神速，大军移动过程不需要时间；兵法无常，他们有可能前往已经攻克的建筑）。
目前除了 1号建筑，其他建筑的保护魔法都尚未被启用，凤凰社决定派出一些成员去其他建筑施用咒语来启动保护魔法。每个凤凰社成员可以瞬间达到任意一个建筑，并用一个小时完成对该建筑保护魔法的启用，之后可以再前往其他的建筑。他们的任务是，保证不论伏地魔大军如何行动，大军所到建筑的保护魔法都已经启用。为了集中更多力量直接打击伏地魔大军，凤凰社希望派出施用咒语的成员数尽可能少。
请你计算，至少需要派出多少位成员。
注：
伏地魔大军到达 1 号建筑开始攻击的同时，凤凰社派出成员去其他建筑施咒。
当大军攻克某个建筑后，凤凰社成员可以在知道大军下一个小时去哪个建筑的情况下，再决定他们去哪些建筑施咒。这个过程也不需要时间。
已经启用过保护魔法的建筑无需再施咒，即便大军攻克该建筑以后某个时候又回到这个建筑，大军也会在这个建筑持续攻击一个小时后再离开。
输入格式
第一行一个整数 n，表示建筑的数量。
接下来 n-1行，每行两个整数 u,v，表示建筑 u 和建筑 v 之间有一条魔法道路。
输出格式
一行一个整数，表示最少需要派出施用咒语的成员数。
输入输出样例
输入 #171 21 32 52 67 24 1输出 #13说明/提示 数据范围
对于 100%的数据，1≤n≤3×105。
CODE
#includeusing namespace std;int lw[300005],bi[600005][2],bs;int n;int dr(){int xx=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9')xx=(xx<<1)+(xx<<3)+ch-'0',ch=getchar();return xx;}void tj(int u,int v){++bs,bi[bs][0]=lw[u],bi[bs][1]=v,lw[u]=bs;}int dfs(int w,int fa,int k){int x=0;for(int o_o=lw[w];o_o;o_o=bi[o_o][0]){int v=bi[o_o][1];if(v!=fa)x+=dfs(v,w,k)+1;}return max(x-k,0);}int main(){n=dr();for(int i=1;i<n;i++){int u=dr(),v=dr();tj(u,v),tj(v,u);}int l=0,r=n-1,mid;while(l+1<r){mid=(l+r)>>1;if(dfs(1,0,mid)==0)r=mid;else l=mid;}printf("%d",r);return 0;}
