题目
点这里看题目。
给定两棵树 \(A,B\)，两棵树均包含 \(n\) 个结点。结点编号均从 \(1\sim n\)。
现在需要给每个编号分配一个权值，使得两棵树上的任意子树内，所有的结点编号对应的权值之和都为 \(1\) 或 \(-1\)。
构造任意一种方案，或声明无解。
所有数据满足 \(1\le n\le 10^5\)。
分析
实际上，找到“子树和”的方案和找到“结点编号”的方案是完全等价的。前者的约束更紧，所以我们可以从“子树和”入手。
设 \(P_u,Q_u\) 分别为 \(A,B\) 树上 \(u\) 的儿子集合，\(s_u,t_u\) 分别为 \(A,B\) 树上 \(u\) 的子树和，而 \(r_1,r_2\) 分别为 \(A,B\) 树的根。则我们相当于要构造 \(s,t\) 满足：
\[\begin{cases} s_{r_1}=t_{r_2}\\ s_u-\sum_{v\in P_u}s_v=t_u-\sum_{v\in Q_u}t_v&\forall 1\le u\le n\\ s_u,t_u\in \{-1,1\}&\forall 1\le u\le n\\ \end{cases} \]如果对模型足够熟悉的话，其实现在已经可以看出来约束描述了一个“欧拉回路”的整数线规，因为：
- 每个变量恰好出现在两条限制中，且符号不同，这相当于一条有向边，向两个结点分别贡献入度和出度。
- 每个变量的取值为 \(\{-1,1\}\)，这相当于是进行“定向”。
- 每条限制为 \(\sum=0\)，这相当于是要求“入度”和“出度”相等。
所以按照这个线规说的建图即可，可以 \(O(n)\) 判断解的存在性和构造解。
如果认不得模型怎么办？我们做一点变换。设 \(s_u=2x_u-1,t_u=2y_u-1\)，则原线规变成：
\[\begin{matrix} \max&0\\ \text{s.t.}&x_{r_1}-y_{r_2}=0\\ &x_u+\sum_{v\in Q_u}y_v=y_u+\sum_{v\in P_u}x_v+\frac{1}{2}(|Q_u|-|P_u|)&1\le u\le n\\ &x_u,y_u\in\{0,1\}&1\le u\le n \end{matrix} \]此时发现有解的必要条件为 \(\forall 1\le u\le n,|P_u|\equiv |Q_u|\pmod 2\)，也就是欧拉回路存在的必要条件（在图连通时就是充要的）。另一方面，当我们把图建出来之后，我们发现它的结构神似“混合图欧拉回路”模型，并且实际上所有初始边都是无向边（比如，你可以通过 \(\frac{1}{2}(|Q_u|-|P_u|)\) 这样的常数推测）。所以，还原回去就可以得到欧拉回路的算法。
Remark.
实际上，在容量全是 \(1\) 的图上 Dinic 复杂度为 \(O(m\times \min\{n^{\frac 2 3},m^{\frac 1 2}\})\)，所以如果没看出来直接跑网络流可能是可以过的。
代码
#include <cstdio>
#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )
const int INF = 1e9;
const int MAXN = 2e5 + 5;
template<typename _T>
inline void Read( _T &x ) {
x = 0; char s = getchar(); bool f = false;
while( s < '0' || '9' < s ) { f = s == '-', s = getchar(); }
while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
if( f ) x = -x;
}
template<typename _T>
inline void Write( _T x ) {
if( x < 0 ) putchar( '-' ), x = -x;
if( 9 < x ) Write( x / 10 );
putchar( x % 10 + '0' );
}
template<typename _T>
inline _T Min( const _T &a, const _T &b ) {
return a < b ? a : b;
}
struct Edge {
int to, nxt;
} Graph[MAXN << 1];
int dir[MAXN];
int head[MAXN], deg[MAXN], cnt = 1;
int S[MAXN], T[MAXN], X[MAXN];
int A[MAXN], B[MAXN];
int N;
inline void AddEdge( const int &from, const int &to ) {
Graph[++ cnt].to = to, Graph[cnt].nxt = head[from];
head[from] = cnt;
}
void DFS( const int &u ) {
for( int &i = head[u], id ; i ; i = Graph[i].nxt )
if( ! dir[id = i >> 1] ) {
dir[id] = i & 1 ? -1 : 1;
DFS( Graph[i].to );
}
}
int main() {
Read( N );
rep( i, 1, N ) {
Read( A[i] );
if( A[i] == -1 ) A[i] = N + 1;
AddEdge( i, A[i] ), AddEdge( A[i], i );
deg[A[i]] ++;
}
rep( i, 1, N ) {
Read( B[i] );
if( B[i] == -1 ) B[i] = N + 1;
AddEdge( i, B[i] ), AddEdge( B[i], i );
deg[B[i]] ++;
}
rep( i, 1, N )
if( deg[i] & 1 )
return puts( "IMPOSSIBLE" ), 0;
puts( "POSSIBLE" );
DFS( 1 );
rep( i, 1, N ) X[i] = S[i] = dir[i];
rep( i, 1, N ) if( A[i] <= N ) X[A[i]] -= S[i];
rep( i, 1, N ) Write( X[i] ), putchar( " \n"[i == N] );
return 0;
}