题目是问把一棵树通过剪边、加边形成一个环的最小代价。
分成两步,先把树剪成一些链,再把链连接成一个环。
设一棵有n个节点的树,剪掉X条边后,形成L条链。
那么代价为X+L。
n-1-X=edgeNum(L条链) ① //原本有n-1条边,剪掉X条,还剩edgeNum(L条链)条
edgeNum(L条链)+L=n ② //L条链的这些边+L条边形成一个有n条边的环
由①、②得到,L=X+1
则代价为 X+L=2*L-1=2*X+1。
问题转化成了,把一棵树剪成一些链,最少能剪成几条链?或者,最少需要剪掉多少条边?
我觉得到了这一步问题就好解决了,我是树形dp搞的,求的是最少能剪成几条链。
dp[u][0]表示u节点是所在链的端点时,以u节点为根节点的子树形成的最少的链数。
dp[u][1]表示u节点是所在链的中间的点时,以u节点为根节点的子树形成的最少的链数。
然后就可以转移了。
#include<cstdio>
#include<cstring>
#include<vector>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int N = ;
const int inf = N; vector<int> G[N];
int dp[N][]; inline int min(int a,int b) {return a<b?a:b;} void dfs(int u,int fa)
{
int sz = G[u].size();
int v,cld=,sum=,min1=inf,min2=inf,temp;
for(int i=;i<sz;i++)
{
v = G[u][i];
if( v!=fa )
{
cld++;
dfs(v,u);
temp = min(dp[v][],dp[v][]);
sum += temp;
temp = dp[v][] - temp;
if( temp<min1 ) {min2=min1;min1=temp;}
else if( temp<min2 ) min2=temp;
}
}
if( !cld ) dp[u][]=,dp[u][]=inf;
else if( ==cld ) dp[u][]=sum+min1,dp[u][]=inf;
else
{
dp[u][] = sum + min1;
dp[u][] = sum + min1 + min2 - ;
}
} int main()
{
int T;
int n,u,v; //freopen("4714.in","r",stdin);
//freopen("myout.txt","w",stdout);
scanf("%d",&T);
while( T-- )
{
scanf("%d",&n);
for(int i=;i<=n;i++) G[i].clear();
for(int i=;i<n-;i++)
{
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(,);
printf("%d\n",*min(dp[][],dp[][])-);
}
return ;
}