ydc题解上写着贪心,后来又说是树形dp。。。可惜看不懂(顺便骗三连)

其实就是每个叶子开始拉一条链,从下面一路走上来,遇到能把两条链合起来的就合起来就好了。

 /**************************************************************
Problem: 1907
User: rausen
Language: C++
Result: Accepted
Time:112 ms
Memory:1396 kb
****************************************************************/ #include <cstdio>
#include <cstring> using namespace std;
const int N = 1e4 + ; struct edge {
int next, to;
edge() {}
edge(int _n, int _t) : next(_n), to(_t) {}
} e[N << ]; struct tree_node {
int fa, ans, used;
} tr[N]; int n;
int first[N], tot; inline int read() {
int x = ;
char ch = getchar();
while (ch < '' || '' < ch)
ch = getchar();
while ('' <= ch && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return x;
} void Add_Edges(int x, int y) {
e[++tot] = edge(first[x], y), first[x] = tot;
e[++tot] = edge(first[y], x), first[y] = tot;
} #define y e[x].to
int dfs(int p) {
int x, cnt = ;
tr[p].ans = , tr[p].used = ;
for (x = first[p]; x; x = e[x].next)
if (y != tr[p].fa) {
tr[y].fa = p;
dfs(y);
tr[p].ans += tr[y].ans;
if (!tr[y].used) ++cnt;
}
if (cnt >= ) tr[p].ans -= , tr[p].used = ;
else if (cnt == ) --tr[p].ans;
}
#undef y int main() {
int i, T;
T = read();
while (T--) {
n = read(), tot = ;
memset(first, , sizeof(first));
for (i = ; i < n; ++i)
Add_Edges(read(), read());
dfs();
printf("%d\n", tr[].ans);
}
return ;
}
05-11 13:19