企业官网建设流程全解析

题目：保卫国王大道

题目描述

维斯特洛大陆上有 N 座城镇，编号从 1 开始，城镇之间由 N−1 条双向通行的国王大道连接起来。国王为了保护在国王大道上通行的百姓不受强盗的侵扰，决定选择一部分城镇作为军营，作为军营的城镇将有足够的兵力来保卫与军营直接相连的几条国王大道。当然，国王的士兵是有限的，所以他想知道，为了保护所有的国王大道，他最少需要设定多少座军营？

输入格式

第一行一个正整数 N，表示有 N 座城镇。

接下来 N 行，每行两个整数 x,y，表示第 x 座城镇与第 y 座城镇之间有一条双向通行的国王大道。

输出格式

输出共一行，输出一个整数表示国王最少需要设定的军营数。

数据范围

2 ≤ N ≤ 2 × 10 5 ， 1 ≤ x , y ≤ N 2≤N≤2×10^5，1≤x,y≤N2≤N≤2×105，1≤x,y≤N

时空限制

1s / 256MB

输入样例1

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

输出样例1

3

输入样例2

15

输出样例2

0

输入样例3

0

输出样例3

1

思路

代码

#include<bits/stdc++.h>usingnamespacestd;constintN=2e5+10;intn,f[N][2];vector<int>g[N];voiddfs(intu){f[u][1]=1;for(inti=0;i<g[u].size();i++){intv=g[u][i];dfs(v);f[u][1]+=min(f[v][0],f[v][1]);f[u][0]+=f[v][1];}}intmain(){cin>>n;for(inti=1;i<n;i++){intx,y;cin>>x>>y;g[x].push_back(y);}dfs(1);cout<<min(f[1][0],f[1][1]);return0;}

结果