HDU 4714

题意：

给出一棵树，设定切断一条边花费跟连接一条边的花费均为1，问将这棵树变为一个圆的最小花费。

钻牛角尖了，钻牛角尖了，一直去抓树的直径，这个时候就体现出队友的重要性了，给了我正确思路，事实上就是将这棵树切成若干棵单支树，要求单支树数量最小，然后再拼起来，就是答案了。

转移状态dp[ i ][ j ],已第I个节点为根的子树的根的可用度数为J的最小单支树数量。每个儿子都可以选择连接父亲与否，推一遍就搞掂了。

因为HDU的编译器原因，用G++，加栈依然会RE，用C++可以AC，所以将DFS改成BFS会更好。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <sstream>
#include <iostream>
#include <algorithm>
#include<cstdlib>
#include<queue>
#pragma comment(linker,"/STACK:1024000000,1024000000")  
using namespace std;#define N 1000005
#define L(x) x<<1
#define R(x) x<<1|1
#define M(x,y) (x + y)>>1
#define MOD 1000000007
#define MODD 1000000006
#define inf 0x7fffffff
#define llinf 0x7fffffffffffffff
#define LL __int64struct edge
{int v,next;
}e[N + N];int dp[N][3],cnt;
int visit[N],mark[N],ans;void addedge(int a,int b)
{e[cnt].v = b;e[cnt].next = visit[a];visit[a] = cnt++;e[cnt].v = a;e[cnt].next = visit[b];visit[b] = cnt++;
}void dfs(int x)
{dp[x][0] = dp[x][1] = dp[x][2] = 1;mark[x] = 1;for(int i = visit[x];i != -1;i = e[i].next){if(mark[e[i].v])continue;dfs(e[i].v);dp[x][0] = min(dp[x][0] + dp[e[i].v][0],dp[x][1] + dp[e[i].v][1] - 1);dp[x][1] = min(dp[x][1] + dp[e[i].v][0],dp[x][2] + dp[e[i].v][1] - 1);dp[x][2] = dp[x][2] + dp[e[i].v][0];}
}int main()
{int i,j,k,l;int n,t;scanf("%d",&t);while(t--){memset(visit,-1,sizeof(visit));ans = 0;scanf("%d",&n);for(i = 1,cnt = 0;i < n;i++){scanf("%d%d",&j,&k);addedge(j,k);}memset(mark,0,sizeof(mark));dfs(1);ans = min(min(dp[1][0],dp[1][1]),dp[1][2]);//    cout<<ans<<endl;printf("%d\n",ans*2 - 1);}return 0;
}