题解 | #小红的字符串生成#

import java.io.*;
import java.util.Arrays;

public class E {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    static StreamTokenizer stmInput = new StreamTokenizer(br);
    static int N = 100010, M = 2 * N;
    static char g[] = new char[N], ans[] = new char[N];
    static int h[] = new int[N], e[] = new int[M], ne[] = new int[M], idx;
    static boolean f[][] = new boolean[N][3];
    static int n, m;

    public static String readString() throws IOException{
        stmInput.nextToken();
        return stmInput.sval;
    }

    public static int readInt() throws IOException {
        stmInput.nextToken();
        return (int) stmInput.nval;
    }

    public static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    // f[u][v]: 在以u为根的子树中, 且节点u为v时, 是否合法
    // d: v=0
    // p: v=1
    public static void dfs(int u, int fa) {
        if (g[u] == 'd') f[u][0] = true;
        else if (g[u] == 'p') f[u][1] = true;
        // ?则二者都能选, 在回溯中看是否合法
        else f[u][0] = f[u][1] = true;

        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (j == fa) continue;
            dfs(j, u);
            f[u][0] &= f[j][1];
            f[u][1] &= f[j][0];
        }
    }

    // 赋值
    public static void dfs1(int u, int fa, char c) {
        ans[u] = c;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (j == fa) continue;
            dfs1(j, u, (c == 'd' ? 'p' : 'd'));
        }
    }

    public static void solve() throws IOException{
        n = readInt();
        String s = readString();
        for (int i = 1; i <= n; i++) g[i] = s.charAt(i - 1);
        Arrays.fill(h, -1);
        for (int i = 0; i < n - 1; i++) {
            int a = readInt(), b = readInt();
            add(a, b);
            add(b, a);
        }
        dfs(1, -1);
        if (g[1] == 'd' && !f[1][0] || g[1] == 'p' && !f[1][1] || !f[1][0] && !f[1][1]) {
            pw.println(-1);
            return;
        }
        if (g[1] == 'd') dfs1(1, -1, 'd');
        else if (g[1] == 'p') dfs1(1, -1, 'p');
        else if (f[1][0]) dfs1(1, -1, 'd');
        else dfs1(1, -1, 'p');
        for (int i = 1; i <= n; i++) pw.print(ans[i]);
    }

    public static void main(String[] args) throws IOException {
//        按照ascii码范围设置为普通字符
        stmInput.ordinaryChars('a', 'z');
        stmInput.wordChars('a', 'z');
        stmInput.ordinaryChars('?', '?');
        stmInput.wordChars('?', '?');

        int T = 1;
        while(T-- != 0){
            solve();
        }

        pw.flush();
        pw.close();
        br.close();
    }

}