codechef Starters73

https://www.codechef.com/START73A?order=desc&sortBy=successful_submissions

Hamiltonian Tree

手玩一下走哈密顿路的过程，一定是，走一条树上路径，然后走过新加的边，再到另一条树上路径，然后走完，然后再走新加的边。

为啥？因为你一条路径走完了，那你不可能走回头路，所以你只能通过新加的边到达另一条路径。

再者，我们注意到，树上路径的任意两条之间点集无交，且所有的路径的点集的并为全集 \(n\)。

也就是说，每个点仅存在于一条路径当中。

考虑最小化新加边，因为有路径数-1=新加边，因此即为最小化路径数。

考虑一个点，要么孤立作为一条路径，要么为路径的两端，要么为路径的中间。其度数对应 \(0,1,2\)。考虑两条路径如果要并起来，显然应该是他们存在两个端点的父亲是一样的，然后通过父亲把他们串起来，因此是可以树上 dp 的，因为我们对于当前点，只需要考虑孤立/连接以某个儿子为端点的一条路径，当前点作为端点/当前点作为中继点，串联起两个儿子为端点的路径。

考虑设 \(dp(u,0/1/2)\) 为 \(u\) 的子树内，当前 \(u\) 点对应哪种情况，所划分出的最小路径数。

转移就很显然啦。

#include <bits/stdc++.h>
#define int long long 
#define pb push_back
#define cal(x) (min(dp[(x)][0],min(dp[(x)][1],dp[(x)][2])))
using namespace std;
const int N=(int)(2e5+5),inf=(int)(2e9);
vector<int>g[N];
int n,dp[N][3];

void clr() {
	for(int i=1;i<=n;i++) g[i].clear(),dp[i][0]=dp[i][1]=dp[i][2]=0;
}

void dfs(int x,int ff) {
	for(int y:g[x]) {
		if(y==ff) continue ;
		dfs(y,x);
	}
	dp[x][0]=dp[x][1]=dp[x][2]=0;
	int res=0;
	for(int y:g[x]) {
		if(y==ff) continue ;
		res+=cal(y);
	}
	dp[x][0]=res+1;
	dp[x][1]=dp[x][2]=inf;
	for(int y:g[x]) {
		if(y==ff) continue ;
		dp[x][1]=min(dp[x][1],min(dp[y][0],dp[y][1])+res-cal(y));
	}
	int mi1=inf,mi2=inf;
	for(int y:g[x]) {
		if(y==ff) continue ;
		int qwq=min(dp[y][0],dp[y][1])-cal(y);
		if(qwq<mi1) mi2=mi1,mi1=qwq;
		else if(qwq<mi2) mi2=qwq;
	}
	if(mi2!=inf) {
		dp[x][2]=res+mi1+mi2-1;
	}
}

void sol() {
	cin>>n;
	for(int i=1;i<n;i++) {
		int x,y; cin>>x>>y;
		g[x].pb(y); g[y].pb(x);
	}
	dfs(1,0);
	int ans=cal(1);
	cout<<ans-1<<'\n';
	clr();
}

signed main() {
	cin.tie(0); ios::sync_with_stdio(false);
	int T; cin>>T; while(T--) sol();
	return 0;
}