E题真的是树形DP

E题真的是树形DP

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
vector<int> e[N];
char s[N];
bool dfs(int u,int fa)
{
    char ch=s[u],c;
    if(ch=='d')c='p';
    else c='d';
    for(auto v:e[u])
    {
        if(v==fa)continue;
        if(s[v]=='?')s[v]=c;
        else if(s[v]==ch)return false;
        if(!(dfs(v,u)))return false;
    }
    return true;
}
int main()
{
	cin>>n;
    scanf("%s",s+1);
	for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    int t=0;
    for(int i=1;i<=n;i++)
    {
        if(s[i]!='?')
        {
            t=i;
            break;
        }
    }
    if(t==0)
    {
        t=1;
        s[1]='d';
    }
    if(dfs(t,-1))cout<<s+1;
    else cout<<-1;
	return 0;
 }