题目保卫国王大道题目描述维斯特洛大陆上有 N 座城镇编号从 1 开始城镇之间由 N−1 条双向通行的国王大道连接起来。国王为了保护在国王大道上通行的百姓不受强盗的侵扰决定选择一部分城镇作为军营作为军营的城镇将有足够的兵力来保卫与军营直接相连的几条国王大道。当然国王的士兵是有限的所以他想知道为了保护所有的国王大道他最少需要设定多少座军营输入格式第一行一个正整数 N表示有 N 座城镇。接下来 N 行每行两个整数 x,y表示第 x 座城镇与第 y 座城镇之间有一条双向通行的国王大道。输出格式输出共一行输出一个整数表示国王最少需要设定的军营数。数据范围2 ≤ N ≤ 2 × 10 5 1 ≤ x , y ≤ N 2≤N≤2×10^51≤x,y≤N2≤N≤2×1051≤x,y≤N时空限制1s / 256MB输入样例17 1 2 1 3 2 4 2 5 3 6 6 7输出样例13输入样例215输出样例20输入样例30输出样例31思路代码#includebits/stdc.husingnamespacestd;constintN2e510;intn,f[N][2];vectorintg[N];voiddfs(intu){f[u][1]1;for(inti0;ig[u].size();i){intvg[u][i];dfs(v);f[u][1]min(f[v][0],f[v][1]);f[u][0]f[v][1];}}intmain(){cinn;for(inti1;in;i){intx,y;cinxy;g[x].push_back(y);}dfs(1);coutmin(f[1][0],f[1][1]);return0;}结果
