小红的树形 dp (树形dp)

: ) 树形dp写法

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,no-stack-protector")
#include <bits/stdc++.h>

using namespace std ;

const int N = 1e6 + 10 ;

std::vector<int> edges[N] ; 
int n ;
int dp[N][2] ; // dp[i , 0/1] 表示以 i 为根节点且为'd'/'p' 的树是否满足任意俩个相邻结点字符不同
char color[N] ; 

void dfs1(int v , int f)
{
	if ( color[v] == '?' ) dp[v][0] = dp[v][1] = 1 ; 
	else if ( color[v] == 'd' ) dp[v][0] = 1 ;
	else dp[v][1] = 1 ; 

	for(auto u : edges[v]) {
		if ( u != f ) {
			dfs1(u , v) ;
			if ( color[v] == '?' ) dp[v][0] &= dp[u][1] , dp[v][1] &= dp[u][0] ;
			else if ( color[v] == 'd' ) dp[v][0] &= dp[u][1] ;
			else dp[v][1] &= dp[u][0] ; 
		}
	}
}

void dfs2(int v,int f) {
	for(auto u : edges[v]) {
		if ( u != f ) {
			if ( color[v] == 'd' ) color[u] = 'p' ;
			else color[u] = 'd' ;
			dfs2(u , v) ;
		}
	}
}
void ret() {
	for(int i = 1 ; i <= n ; i++) cout << color[i] ; 
}

int main()
{
	ios::sync_with_stdio(false) ;
	cin.tie(0) ;
	cout.tie(0) ;

	cin >> n >> color + 1 ;

	for(int i = 1 ; i < n ; i++) {
		int u , v ;
		cin >> u >> v ;
		edges[u].push_back(v) ;
		edges[v].push_back(u) ;
	}

	dfs1(1 , 0) ;


	if ( color[1] == '?' ) 
	{
		if ( !dp[1][0] && !dp[1][1] ) cout << -1 << '\n' ;
		else {
			if ( dp[1][0] ) color[1] = 'd' ; else color[1] = 'p' ;
            dfs2(1 , 0)  ;
            ret() ; 
		}
	} 
	else if ( color[1] == 'd' )
    {
        dfs2(1 , 0) ;
        if ( dp[1][0] ) ret() ; else cout << -1 << '\n' ;
    }
	else {
        dfs2(1 , 0) ;
        if ( dp[1][1] ) ret() ; else cout << -1 << '\n' ;
    } 

	return 0 ; 
}