dp学习笔记

题目 题意: n个点的树，每个节点具有一种颜色。任选一个点作为根，使得所有以非根为节点的子树满足颜色一致。 思路: 找规律，如果存在某个点满足所有特殊边都连过他，即满足。特殊边是指连接不同颜色的边。 或者树形dp，但是难度有些高。先一遍dfs求出以1为根是否满足条件，之后再dfs。如果某个点的所有儿子均满足条件，可；否则，只有当有且仅有一个儿子不满足条件且当前节点与父节点同色，且其他儿子与当前节点同色且满足条件才行。日，打死俺也想不出来的换根dp. 时间复杂度: O(n) 代码:

// Problem: A. Timofey and a tree
// Contest: Codeforces - Codeforces Round #395 (Div. 1)
// URL: https://codeforces.com/problemset/problem/763/A
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
using namespace std;
const int N = 1e5+10;
int n,m,k,T;
int a[N];
vector va[N];
bool f[N]; //以i为根是否同色
void dfs(int cur,int fa)
{
	f[cur] = 1;
	for(int j:va[cur])
	{
		if(j==fa) continue;
		dfs(j,cur);
		if(!f[j]||a[cur]!=a[j]) f[cur]=0;
	}
}
int dfs2(int cur,int fa)
{
	// cout