题解 | # F Train Wreck#

F 题

邻接表 + 优先队列 + 贪心

思路

(1) 建树 — 邻接表

初始时，只有根节点 (序号0)，遇到 '(' 即入栈时 则建立新节点，遇到 ')' 即出栈时，则执行"退后操作"
建立新节点时，新节点的序号为入栈序号，新节点的父亲为 now 结点 

now 结点，指当前我们指向的结点
因此，建立新节点 即 新建一个 now 结点的子节点，"退后操作" 即 让 now 指向 now 的父节点

建好树后，共有 n+1 个结点，n 条边
n+1 个结点，指最初的 0 结点 与 新建的 n 个新节点

(2) "染色" — 贪心 + 优先队列

建好树后，问题转换为：对树的 n 个结点 (0结点不染色) 进行染色，且染色完毕后，
我们需做到：n+1 个结点(包括了0结点)中，任意结点 A ，其直接子节点中，不存在两个颜色相同的 

Code

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int>PII;

const int N = 1e7+10;

int n;
bool flag;
char s[N];
PII p[N]; 
int e[N],ne[N],h[N],idx;
int fa[N],color[N],ans[N];
priority_queue<PII>q;

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

void dfs(int u){
    if(flag) return ;

    int t=0;
    for(int i=h[u];i!=-1;i=ne[i]){ // 我的子节点不能存在两两同色
        int j=e[i];
        if(q.size()>0) {
            auto it=q.top();  // 选当前队列中数目最多的颜色
            ans[j]=it.second;
            q.pop(); // 该颜色用过了，所以得先出列一下，避免再次被选到，之后还会回来的
            if(it.first-1>=1) p[t++]={it.first-1,it.second};
        }   
        else { flag=true; return ; }
    }

    for(int i=0;i<t;i++) q.push(p[i]);  // 上面出列的，再进去。当然，数目要减去 1 

     for(int i=h[u];i!=-1;i=ne[i]){
         int j=e[i];
         dfs(j);
         if(flag) return ;
     }

}

int main(){
    scanf("%d%s",&n,s+1);
    for(int i=1;i<=n;i++) {  int x;  scanf("%d",&x),color[x]++;  }

    for(int i=1;i<=n;i++)  if(color[i]) q.push({color[i],i});

    int now=0,t=0; 
    memset(h,-1,sizeof h);
    for(int i=1;i<=2*n;i++){
        if(s[i]=='(') ++t,fa[t]=now,add(now,t),now=t;  // 建树/有向图
        else now=fa[now];
    }

    dfs(0);

    if(flag) puts("NO");
    else {
        puts("YES");
        for(int i=1;i<=n;i++) {
            if(i==1) printf("%d",ans[i]);
            else printf(" %d",ans[i]);
        }
    }

    return 0;
}