C++(g++ 7.5.0) 解法, 执行用时: 382ms, 内存消耗: 23972K, 提交时间: 2023-04-26 18:20:40

#include <cstdio>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
using PII = pair<int,int>;
const int maxn = 200000 + 5;

int n, siz[maxn], son[maxn];
int tot, L[maxn], R[maxn], rdfn[maxn];
vector<int> edge[maxn];

void getsz(int u) {
  L[u] = ++tot;
  rdfn[tot] = u;
  siz[u] = 1;
  for (int v: edge[u]) {
    getsz(v);
    siz[u] += siz[v];
    if (siz[v] > siz[son[u]]) {
      son[u] = v;
    }
  }
  R[u] = tot;
}

int push(int u) {
  putchar('+');
  printf("%d", u);
  return 1;
}
int pushTree(int u) {
  for (int i = L[u]; i <= R[u]; i++) {
    push(rdfn[i]);
  }
  return R[u] - L[u] + 1;
}
void pop(int len = 1) {
  while (len--) {
    putchar('-');
  }
}
void ok(int u) {
  putchar('=');
  printf("%d", u);
}

void solve(int u) {
  int sz = 0;
  for (int x = u; x; x = son[x]) {
    ok(x);
    sz += push(x);
    for (int v: edge[x]) {
      if (v == son[x]) continue;
      sz += pushTree(v);
    }
  }
  priority_queue<PII, vector<PII>, greater<PII> > pq;
  for (int x = u; x; x = son[x]) {
    for (int v: edge[x]) {
      if (v == son[x]) continue;
      pq.emplace(siz[v], v);
    }
  }
  if (pq.empty()) return ;
  pop(sz);
  vector<PII> ch;
  while (pq.size() >= 2) {
    auto x = pq.top(); pq.pop();
    auto y = pq.top(); pq.pop();
    if (x.first > y.first) swap(x, y);
    ch.emplace_back(x.second, y.second);
    pq.emplace(x.first + y.first, ch.size() + n);
  }
  function<int(int)> add = [&](int u) {
    if (u <= n) {
      return pushTree(u);
    } else {
      u -= n + 1;
      return add(ch[u].first) + add(ch[u].second);
    }
  };
  function<int(int)> dfs = [&](int u) {
    if (u <= n) {
      solve(u);
      return siz[u];
    } else {
      u -= n + 1;
      int sz = add(ch[u].second);
      sz += dfs(ch[u].first);
      pop(sz);
      add(ch[u].first);
      dfs(ch[u].second);
      return sz;
    }
  };
  for (int x = u; x; x = son[x]) {
    push(x);
  }
  dfs(pq.top().second);
}

int main() {
  scanf("%d", &n);
  for (int i = 2; i <= n; i++) {
    int fa;
    scanf("%d", &fa);
    edge[fa].push_back(i);
  }
  getsz(1);
  solve(1);
  puts("!");
  return 0;
}

C++(clang++11) 解法, 执行用时: 360ms, 内存消耗: 25116K, 提交时间: 2020-11-30 18:10:03

#include<bits/stdc++.h>
using namespace std;
void add(int x){
	printf("+%d",x);
}
void sub(){
	putchar('-');
}
void interview(int x){
	printf("=%d",x);
}
const int maxn=100010;
vector<int>v[maxn];
int n,hv[maxn],fa[maxn],si[maxn];
void dfs(int x){
	si[x]=1;
	for(int y:v[x]){
		if(y!=fa[x]){
			dfs(y);
			si[x]+=si[y];
			if(si[hv[x]]<si[y])hv[x]=y;
		}
	}
}

void go(int x){
	add(x);
	for(int y:v[x])
	if(y!=fa[x])go(y);
}
void pop(int x){
	for(int i=1;i<=si[x];i++)
	sub();
} 
void sv1(int x);
void sv2(const vector<int>&v){
	if(v.empty())return;
	if(v.size()==1){
		sv1(v[0]);
		return;
	}
	int t=0,s=0;
	vector<int>l,r;
    for(int x:v)
    s+=si[x];
    for(int x:v){
    	t+=si[x];
    	if(l.size()&&t>s/2)r.push_back(x);
    	else l.push_back(x);
	}
	for(int x:l)go(x);
	sv2(r);
	for(int x:l)pop(x);
	for(int x:r)go(x);
	sv2(l);
	for(int x:r)pop(x);
	return;
}
void sv1(int x){
    vector<int>p;
    for(int y=x;y;y=hv[y]){
    	interview(y);
    	add(y);
    	for(int z:v[y]){
    		if(z!=fa[y]&&z!=hv[y]){
    			go(z);
    			p.push_back(z);
			}
		}
	}
	pop(x);
	int t=0;
	for(int y=x;y;y=hv[y])
	add(y),t++;
	sv2(p);
	while(t--)sub();
}
int main(){
	cin>>n;
	for(int i=2;i<=n;i++){
		scanf("%d",&fa[i]);
		v[fa[i]].push_back(i);
	}
	dfs(1);
	sv1(1);
	putchar('!');
}