HDU4714 Tree2cycle 解题报告

题意

给定一棵无根树,删除或连接一条边的代价为\(1\),求把树变为环的最小代价.

前置思路

如果删除了\(k\)条边,使得树变成\((k+1)\)条链,再用\((k+1)\)次连接操作把树变成一个环,那么总代价为\((2 \times k +1)\).

问题转化为求\(k\)的最小值,即最少能将一棵树分为多少条链.

思路1 树形DP

树形DP求最少能将一棵树分为多少条链.

采用像极了CF633F的思路,设\(DP[i][0]\)表示最少能将\(i\)的子树分为多少条链,\(DP[i][1]\)表示在\(i\)的子树中有一条可以向上继续拓展的链的情况下,最少能将\(i\)的子树分为多少条链.

如果我们令\(1\)节点为树根,答案即为\(DP[1][0]\).

状态转移方程:

如果我们记\(F(u)=DP[u][1]-DP[u][0]\).那么:

\[DP[u][1]=\min(F(v))
+\sum_vDP[v][0]\quad (v\in son(u))\]

\(\min(F(v))\)的含义是,找一条可以向上继续拓展的链,使它继续向上扩展.

\[DP[u][0]=\min(F(v))+ \min2(F(v))
+\sum_vDP[v][0]\quad (v\in son(u))\]

其中\(\min2( )\)表示非严格次小值.

\(\min(F(v))+ \min2(F(v))\)的含义是,找两条可以继续向上扩展的链,在\(u\)点把他们接在一起.

代码:

#include<bits/stdc++.h>

const int SIZE=200005,INF=0x3F3F3F3F;

int head[SIZE],nex[SIZE],to[SIZE],P,DP[SIZE][2];

void Link(int u,int v)

{

	nex[++P]=head[u];head[u]=P;to[P]=v;

	nex[++P]=head[v];head[v]=P;to[P]=u;

}

int F(int u){return DP[u][1]-DP[u][0];}

void DFS(int u,int Fa)

{

	int min1=INF,min2=INF,Cnt=0,sum=0;

	for(int i=head[u];i;i=nex[i])

	{

		int v=to[i];

		if(v==Fa)continue;

		DFS(v,u);

		++Cnt;

		sum+=DP[v][0];

		if(min1>F(v))min1=F(v);

		else if(min2>F(v))min2=F(v);

	}

	if(Cnt==0)DP[u][1]=DP[u][0]=1;

	else if(Cnt==1)DP[u][1]=DP[u][0]=std::min(sum+1,sum+min1);

	else

	{

		DP[u][1]=sum+min1;

		DP[u][0]=std::min(sum+min1+min2-1,DP[u][1]);

	}

} 

int main()

{

	int n,u,v;

	scanf("%d",&n);

	for(int i=1;i<n;i++)

	{

		scanf("%d%d",&u,&v);

		Link(u,v);

	}

	DFS(1,0);

	printf("%d",2*DP[1][0]-1);

	return 0;

}

思路2 贪心

本题贪心过程非常巧妙,可以通过DFS遍历整棵树,回溯时,如果一个节点的度数\(>2\),就删掉多余的点,优先删父节点,这样可以使回溯到父节点时的答案更优,这一步答案也不会更劣.

巴特西

HDU4714 Tree2cycle 解题报告

题意

前置思路

思路1 树形DP

思路2 贪心

最新文章

热门文章