SGU 321 知道了双端队列，

思路： 贪心。

每次删除最上面的边。。

#include<utility>

#include<iostream>

#include<vector>

#include<cstring>

#include<deque>

#include<cstdio>

#include<algorithm>

using namespace std;

const int M = 200008;

deque <int > q;

vector <int> vi;

int first_edge[M],next_edge[M],to[M],ty[M],sum;

void dfs(int u){

    if(sum < 0){

        sum += 2;

        ty[q.front()] *= -1;

        vi.push_back(q.front());

        q.pop_front();

    }

    for(int i = first_edge[u] ; i!=-1 ; i = next_edge[i]){

        sum += ty[i];

        if(ty[i] == -1)q.push_back(i);

        dfs(to[i]);

        if(ty[i] == -1){

            q.pop_back();

        }

        sum -= ty[i];

    }

}

int main(){

    freopen("input.txt","r",stdin);

    int n,m,u,v;

    sum = 0;

    char buf[10];

    memset(first_edge,-1,sizeof(first_edge));

    scanf("%d",&n);

    for(int i = 0; i < n-1; i++){

       scanf("%d%d%s",&u,&v,buf);

       next_edge[i]  = first_edge[v];

       first_edge[v] = i;

       ty[i] = *buf == 'p' ? 1 : -1;

      // cout <<ty[i] <<endl;

       to[i] = u;

       if(*buf == 'a')scanf("%s",buf);

    }

    dfs(1);

    printf("%d\n",(int)vi.size());

    for(int i = 0; i < vi.size(); i++){

        printf("%d%c",vi[i]+1, i==vi.size() - 1 ? '\n': ' ');

    }

}