题目

给出一棵树，要求你为树上的结点标上权值，权值可以是任意的正整数

唯一的限制条件是相邻的两个结点不能标上相同的权值，要求一种方案，使得整棵树的总价值最小。

分析

每个结点的权值最大可能为 \(\log{n}\)。

所以直接设 \(dp[x][y]\) 表示点 \(x\) 选择的权值为 \(y\) 时的最小总价值，

维护最大值和次大值就可以做到 \(O(n\log{n})\)

代码

#include 
#include 
using namespace std;
const int N=10011; vectorG[N];
int dp[N][21],n,fi[N],se[N],ans=0x3f3f3f3f;
void dfs(int x,int fa){
	int len=G[x].size();
	dp[x][0]=0x3f3f3f3f;
	for (int i=1;i<=20;++i) dp[x][i]=i;
	for (int i=0;idp[x][i]) se[x]=fi[x],fi[x]=i;
	    else if (dp[x][se[x]]>dp[x][i]) se[x]=i; 
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for (int i=1;i>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(1,0);
	for (int i=1;i<=20;++i)
	    if (ans>dp[1][i]) ans=dp[1][i];
	return !printf("%d",ans);
}