广告网站开发背景,网络推广方案七步法,网站建设开发案例教程,网页版微信怎么扫描二维码description
戳我看题目
solution
正解说是欧拉回路#xff0c;但是于私而言非常难懂#xff0c;如果有兴趣可以看香香mm的博客 定义一个点如果有偶数个儿子#xff0c;就为奇点#xff1b;如果有奇数个儿子#xff0c;就为偶点 对于一个点的每个子树自身是满足mod21mo…description
戳我看题目
solution
正解说是欧拉回路但是于私而言非常难懂如果有兴趣可以看香香mm的博客 定义一个点如果有偶数个儿子就为奇点如果有奇数个儿子就为偶点 对于一个点的每个子树自身是满足mod21mod\ 21mod 21的
如果是偶点那么奇数个儿子相加mod2mod\ 2mod 2就已经满足要求了点权就设为000 如果是奇点那么偶数个儿子相加取模就没了点权应该设为±1±1±1
单思考一个子树的情况算上自己整棵树内的奇点个数应为2k12k12k1 随便两两匹配后一定会孤出一个点来 这个点就通过uuu点往上跟某一个孤的祖先匹配
两两匹配的点对就分别取1,−11,-11,−1二分图染色可以搞
code
#include cstdio
#include vector
#include iostream
using namespace std;
#define maxn 100005
int f[maxn], c[maxn], rnk[maxn];int find( int u ) {if( u f[u] ) return u;int fa find( f[u] );c[u] ^ c[f[u]];return f[u] fa;
}void merge( int u, int v ) { //并查集按秩合并 int fu find( u ), fv find( v );if( fu fv ) return;else if( rnk[fu] rnk[fv] ) swap( fu, fv );else if( rnk[fu] rnk[fv] ) rnk[fu] ;c[fv] c[u] ^ c[v] ^ 1;f[fv] fu;
} struct node {vector int G[maxn];int siz[maxn];int root;void init( int n ) {for( int i 1, fa;i n;i ) {scanf( %d, fa );if( ~ fa ) G[fa].push_back( i ), siz[fa] ;else root i;}}int dfs( int u ) {vector int num;if( ! ( siz[u] 1 ) ) num.push_back( u );//有偶数个儿子 即奇点 for( int i 0;i G[u].size();i )num.push_back( dfs( G[u][i] ) );for( int i 1;i num.size();i 2 ) //一定是2k1个点 两两匹配 孤出一个点与上面祖先匹配merge( num[i], num[i 1] );return num[0]; }}A, B;int main() {int n;scanf( %d, n );A.init( n ), B.init( n );for( int i 1;i n;i )if( ( A.siz[i] B.siz[i] ) 1 ) //i点在两棵树上的奇偶性应一致 return ! printf( IMPOSSIBLE\n );printf( POSSIBLE\n );for( int i 1;i n;i ) f[i] i;A.dfs( A.root ), B.dfs( B.root );for( int i 1;i n;i )if( ! ( A.siz[i] 1 ) ) {find( i );if( c[i] ) printf( 1 );else printf( -1 );}else printf( 0 );return 0;
}
