题目链接
可能是个树上 DP？指针真好玩 23333。
首先对于所有玩具如果有深度差超过 1 的就是无解（在这里贡献 WA * 3），所以 dfs 一遍记录深度是有必要的……
然后如果有一个点的两颗子树中都含有最小、最大深度，那么这种情况也是无解，可以令同时含有两种深度的子树 tag = 1。
然后考虑最少交换次数，对于每一个节点的左右子树，三种情况需要交换：
1. 左边全是小深度的，右边全是大深度的
2. 左边全是小深度的，右边大小深度都有
3. 左边大小深度都有，右边全是大深度的
root->cnt = left_child->cnt + right_child->cnt + 本次是否需要交换（0 or 1）。
所以代码判的挺多的……
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int maxn = + ;
int n, in_deg[maxn], maxx, minn, ans, node_num; struct Node {
int deep, cnt, tag, type;
Node *lchild, *rchild; Node() { type = cnt = deep = , lchild = rchild = NULL; }
~Node() {};
} node[maxn], *p_root; inline int read() {
register char ch = ; register int w = , x = ;
while( !isdigit(ch) ) w |= (ch == '-'), ch = getchar();
while( isdigit(ch) ) x = (x * ) + (ch ^ ), ch = getchar();
return w ? -x : x;
} inline void Set_deep(Node *x) {
if( x->lchild != NULL ) x->lchild->deep = x->deep + , Set_deep(x->lchild);
if( x->rchild != NULL ) x->rchild->deep = x->deep + , Set_deep(x->rchild);
} inline void Deep_fs(Node *x) {
if( x->lchild == NULL && x->rchild == NULL ) return ;
if( x->lchild != NULL ) Deep_fs(x->lchild);
if( x->rchild != NULL ) Deep_fs(x->rchild);
if( x->lchild->tag && x->rchild->tag ) ans = -;
if( x->lchild->type ^ x->rchild->type ) x->tag = ;
else if( x->lchild->tag | x->rchild->tag ) x->tag = ;
else if( x->lchild->deep != x->rchild->deep ) x->tag = ;
x->cnt = x->lchild->cnt + x->rchild->cnt;
x->deep = max(x->lchild->deep, x->rchild->deep);
if( x->lchild->tag ^ x->rchild->tag ) {
if( x->lchild->tag && x->lchild->deep == x->rchild->deep ) ++x->cnt;
if( x->rchild->tag && x->lchild->deep < x->rchild->deep ) ++x->cnt;
} else if( x->lchild->deep < x->rchild->deep ) ++x->cnt;
} int main(int argc, const char *argv[])
{
freopen("..\\nanjolno.in", "r", stdin);
freopen("..\\nanjolno.out", "w", stdout); scanf("%d", &n), node_num = n, minn = 2e9;
for(int l, r, i = ; i <= n; ++i) {
l = read(), r = read();
if( l == - ) node[++node_num].type = , node[i].lchild = &node[node_num];
else node[i].lchild = &node[l], ++in_deg[l];
if( r == - ) node[++node_num].type = , node[i].rchild = &node[node_num];
else node[i].rchild = &node[r], ++in_deg[r];
}
for(int i = ; i <= n; ++i) if( in_deg[i] == ) p_root = &node[i];
p_root->deep = , Set_deep(p_root);
for(int i = ; i <= node_num; ++i) if( node[i].type ) {
maxx = max(maxx, node[i].deep), minn = min(minn, node[i].deep);
}
if( maxx - minn > ) puts("-1");
else Deep_fs(p_root), printf("%d\n", ans == - ? ans : p_root->cnt); fclose(stdin), fclose(stdout);
return ;
}
—— “从你慷慨的手里所付予的，我都接受。我别无所求。”
“是了，是了，我懂得你，谦卑的乞丐，你是乞求一个人的一切所有。”