問題概要
頂点数 の木が与えられる．木の情報はそれぞれ
要素からなる二つの配列
によって与えられ，各
に対し，辺
が存在することを表す．また，頂点
が一つ指定される．
この木の頂点のそれぞれに対し， 〜
の整数をこの順に一つずつ配置していく．各値をどの頂点に配置するかは自由に決められるが，配置しようとしている頂点と
を結ぶパス上（端点を含む）に一つも値が配置されていない状態でなければならない．従って，各頂点には高々一つの値が配置される
個の値を全て配置できる配置方法の総数を求めよ．
解法
個の値を全て配置し終わった状態を考えてみると，
〜
の各値に対し，相異なる頂点が丁度一つずつ対応付けられていることが分かります．
番目に配置する頂点の番号を
とする列
を考えると，
は
〜
の順列の一つになっています．ですが，任意の順列が valid なわけではありません（例えば，根から近い順に頂点を並べると
のとき無理）．順列が与えられたときに，それに対する正当性判定が必要になります．ところで，大きさ
の順列の総数は
個しかない（制約から，十分扱えるサイズ）ので，ある順列に対する正当性判定をある程度高速に行えれば，valid な順列を一つずつ数え上げることができます．
正当性判定は，各頂点に値が配置されているかどうかを覚えておいて，問題文で与えられた条件を満たすか否かをナイーブに判定することで行えます． 番目の値を配置可能か否かは，
から
までのパス上の頂点全てが，何も配置されていないかどうかを調べれば分かります．
へのパスを辿るために，予め
を始点とする DFS をして木を有向化したものを作っておくと単純な for ループで処理できます．valid な操作だったら，頂点
の配置済みフラグを更新することで，続く値についても判定ができます．全てのステップで valid なら，その順列は valid であると分かります．
判定するべき順列の総数が 個であり，一つの順列に対する判定では（長さ
の）パスを辿る操作を
回するので，全体では
時間になります．
コード
using VI = vector< int >; using VVI = vector< vector< int > >; #define REP2( i, n ) REP3( i, 0, n ) #define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i ) #define GET_REP( a, b, c, F, ... ) F #define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ ) #define FOR( e, c ) for ( auto &e : c ) #define ALL( c ) ( c ).begin(), ( c ).end() #define SZ( v ) ( (int)( v ).size() ) #define PB push_back class OneEntrance { public: int N; VVI G; VI prev; int count( vector <int> a, vector <int> b, int s ) { N = SZ( a ) + 1; G = VVI( N ); prev = VI( N ); REP( i, N - 1 ) { G[ a[i] ].PB( b[i] ); G[ b[i] ].PB( a[i] ); } dfs( s, -1 ); VI ord( N ); iota( ALL( ord ), 0 ); int res = 0; do { VI counts( N ); bool ok = true; FOR( v, ord ) { for ( int c = v; c != -1; c = prev[c] ) { ok &= counts[c] == 0; } counts[v] = 1; } res += ok; } while ( next_permutation( ALL( ord ) ) ); return res; } void dfs( const int u, const int p ) { prev[u] = p; FOR( v, G[u] ) { if ( v == p ) { continue; } dfs( v, u ); } return; } };
