一眼题...

  f[i][0]表示在i连接一个子树的最小值,f[i][1]表示在i连接两个子树的最小值,随便转移...

  样例挺强的1A了美滋滋...

UPD:学习了2314的写法之后短了好多T T

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=, inf=1e9;
struct poi{int too, pre;}e[maxn];
int n, T, tot, x, y;
int f[maxn][], last[maxn];
void read(int &k)
{
int f=; k=; char c=getchar();
while(c<'' || c>'') c=='-' && (f=-), c=getchar();
while(c<='' && c>='') k=k*+c-'', c=getchar();
k*=f;
}
inline void add(int x, int y){e[++tot]=(poi){y, last[x]}; last[x]=tot;}
inline int min(int a, int b){return a<b?a:b;}
void dfs(int x, int fa)
{
f[x][]=maxn; f[x][]=; int sum=;
for(int i=last[x], too;i;i=e[i].pre)
if((too=e[i].too)!=fa)
{
dfs(too, x);
f[x][]=min(f[x][]+min(f[too][], f[too][]), f[x][]+f[too][]-);
f[x][]=min(f[x][]+min(f[too][], f[too][]), sum+f[too][]);
sum+=min(f[too][], f[too][]);
}
}
int main()
{
read(T);
while(T--)
{
read(n); memset(last, , (n+)<<); tot=;
for(int i=;i<n;i++) read(x), read(y), add(x, y), add(y, x);
dfs(, ); printf("%d\n", min(f[][], f[][]));
}
}

旧代码:

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=, inf=1e9;
struct poi{int too, pre;}e[maxn];
int n, T, tot, x, y;
int f[maxn][], last[maxn];
void read(int &k)
{
int f=; k=; char c=getchar();
while(c<'' || c>'') c=='-' && (f=-), c=getchar();
while(c<='' && c>='') k=k*+c-'', c=getchar();
k*=f;
}
inline void add(int x, int y){e[++tot]=(poi){y, last[x]}; last[x]=tot;}
inline int min(int a, int b){return a<b?a:b;}
void dfs(int x, int fa)
{
int mn1=inf, mn2=inf, mni1=, mni2=, tmp=; f[x][]=; f[x][]=-;
for(int i=last[x], too;i;i=e[i].pre)
if((too=e[i].too)!=fa)
{
dfs(too, x);
f[x][]+=min(f[too][], f[too][]);
if(f[too][]==min(f[too][], f[too][])) tmp=;
if(f[too][]-min(f[too][], f[too][])<mn1) mn1=f[too][]-min(f[too][], f[too][]), mni1=too;
else if(f[too][]-min(f[too][], f[too][])<mn2) mn2=f[too][]-min(f[too][], f[too][]), mni2=too;
}
f[x][]+=tmp;
if(!(f[x][]-tmp)) {f[x][]=; f[x][]=inf; return;}
if(mn2==inf) {f[x][]=inf; return;}
for(int i=last[x], too;i;i=e[i].pre)
if((too=e[i].too)!=fa)
{
if(too==mni1 || too==mni2) f[x][]+=f[too][];
else f[x][]+=min(f[too][], f[too][]);
}
}
int main()
{
read(T);
while(T--)
{
read(n); memset(last, , (n+)<<); tot=;
for(int i=;i<n;i++) read(x), read(y), add(x, y), add(y, x);
dfs(, ); printf("%d\n", min(f[][], f[][]));
}
}
05-27 23:46