AGC005
A
给定一个仅由ST构成的串X。执行如下操作\(10^{10000}\)次：
如果X包含ST子串，就把第一个ST子串删掉。
直接用一个栈模拟就可以了。
B
给定一个序列\(a_1\dots a_n\)。
求\(\sum_{1\le l\le r\le n}\min_{l\le i\le r}a_i\)。
枚举这个\(\min a_i\)，
那么答案就是求\(\sum_{x}x\sum_{1\le l\le r\le n}[\min_{l\le i\le r}a_i = x]\)。
显然对于所有\(\sum_{1\le l\le r\le n}[\min_{l\le i\le r}a_i = x]>0\)的\(x\)存在\(i\)使得\(x=a_i\)。
如果\(a_i\not=a_j\)，那么\([\min_{l\le i\le r}a_i = a_x]\)当且仅当\(l\le x\le r\)且\(\forall _{l\le i\le r}a_i\ge a_x\)。
枚举\(a_i\)，然后\(a_j<a_i\)的所有\(j\)都不能包含在区间内。找到\(j_1=j<i\)的最大\(j\)，和\(j_2=j>i\)的最小\(j\)。那满足条件的区间数就是\((j_2-i)(i-j_1)\)。
怎么找到\(j_1,j_2\)呢？从小到大枚举，然后枚举完以后扔进set表示不能选择。
如果\(a_i\)可以\(=a_j\)，那怎么办？
这种情况直接随机顺序然后按照上面说的set维护也是可以的。
时间复杂度\(O(n\log n)\)。
C
给定\(a_1\dots a_n\)，判断是否存在一棵树满足第\(i\)个点离最远点的距离为\(a_i\)。
结论：
- 每个点的最远点都在一条直径的一个端点上。
- 如果直径长度为偶数，所有直径交于一点。
- 如果直径长度为奇数，所有直径交于一边。
设\(b_x=\sum [a_i=x],m=\max a_i\)。
那么存在一棵树当且仅当：
m是奇数：
\[ b_1\dots b_{\lfloor \frac{m}{2}\rfloor}=0\\ b_{\lceil \frac{m}{2}\rceil}=2\\ b_{\lceil \frac{m}{2}\rceil+1}\dots b_m\ge 2 \]
m是偶数：
\[ b_1\dots b_{\frac{m}{2}-1}=0\\ b_{\frac{m}{2}}=1\\ b_{\frac{m}{2}+1}\dots b_m\ge 2 \]
D
给定\(n,k\)，求有多少个排列\(a_1\dots a_n\)满足\(|a_i-i|\not=k\)。
建一个二分图，令\(X_i\)匹配\(Y_j\)等价于\(a_i=j\)。
若\(|i-j|=k\)，那么\(X_i\)向\(Y_j\)连一条红边，否则连一条蓝边。
则原问题等价于求全是蓝边的完美匹配数。
经典容斥：\(ans=\sum_{i=0}^n(-1)^i(n-i)!b_i\)，其中\(b_i\)表示匹配\(i\)条红边的方案数。
实际上如果只考虑红边，那么形成了一些链。
那就把链给抽出来。分别DP然后背包合并。
E
有\(n\)个点，n-1条红边n-1条蓝边，分别构成了一棵红树和一棵蓝树。
一开始A在X点，B在Y点。
从A开始，每个人可以进行一次操作：
不动或者选一条边走到另一端，其中A只能走红边，B只能走蓝边。
若A,B相遇则结束。A希望轮数最多。B希望轮数最少。求最终轮数。
如果存在一条红边，它两端在蓝树上距离>2，那么如果A能安全到达其中一段，就永远不会结束。
否则？
考虑从A开始BFS。如果一个点离A的距离\(\le\)离B的距离，那么A到达这个点后（或者到达之前）B一定可以让游戏结束了
否则可以继续从这个点BFS。
然后最优的策略显然就是去到能到达的离B最远的点然后不动了。
F
有一棵树，对于\(k=1\dots n\)， 求出对于在\(n\)个点选出\(k\)个点这\(\binom{n}{k}\)种方案，包含这些点的最小联通块的点数的和。
显然这个联通块点数=边数+1。那么我们只需要算出边数和\(+\binom{n}{k}\)。
边数和又可以拆成每一条边出现次数的和。
一条边出现显然当且仅当两边都有被选出的点。那么对于一条边的出现次数，假设一边点数是\(x\)，显然可以容斥：
\(cnt=\binom{n}{k}-\binom{x}{k}-\binom{n-x}{k}\)。
这样可以\(O(n^2)\)算了。
显然是不够的。
除了\(\binom{n}{k}\)以外，记\(-\binom{x}{k}\)的出现次数为\(a_x\)，
那么答案就是\(ans_k=n\binom{n}{k}-\sum_{x}a_x\binom{x}{k}\)。
记\(c_k=\sum_{x}a_x\binom{x}{k}\Leftrightarrow c_kk!=\sum_{x}a_xx!\frac{1}{(x-k)!}\)
设\(A_k=A_kk!,B_k=\frac{1}{(n-k)!}\)，那么\(c_kk!=\sum_x A_xB_{n+k-i}\)。
若\(C_{k+n}=c_{k}k!\)，那就直接\(C_{k}=\sum_x A_xB_{k-x}\)。直接NTT！原根是5！
Code
A
/*
Author: QAQ-Automaton
LANG: C++
PROG: a.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// print a signed integer
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
char stk[200005],s[200005];
int t;
void add(char c){
if(!t||c=='S'||stk[t]!='S')stk[++t]=c;
else --t;
}
int main(){
#ifdef QAQAutoMaton
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
scanf("%s",s);
for(char *a=s;*a;++a)add(*a);
write(t,'\n');
return 0;
}
B
/*
Author: QAQ-Automaton
LANG: C++
PROG: b.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>ll dcmp(T a,T b){return a>b;}
template<ll *a>ll cmp_a(ll x,ll y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const ll SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; ll f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// prll the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed lleger
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// prll a signed lleger
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
ll a[200005],b[200005];
set<ll> f;
int main(){
#ifdef QAQAutoMaton
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
#endif
ll n;
read(n);
for(ll i=1;i<=n;++i){
read(a[i]);
b[a[i]]=i;
}
f.insert(0);
f.insert(n+1);
ll ans=0,s;
for(ll i=1;i<=n;++i){
set<ll>::iterator a=f.lower_bound(b[i]);
s=*a-b[i];
--a;
s*=(b[i]-*a);
ans+=s*i;
f.insert(b[i]);
}
write(ans,'\n');
return 0;
}
C
/*
Author: QAQ-Automaton
LANG: C++
PROG: c.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// print a signed integer
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
int a[200005],b[200005];
void check(bool a){
if(!a){write("Impossible\n");exit(0);}
}
int main(){
#ifdef QAQAutoMaton
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
#endif
int n;
read(n);
for(int i=1;i<=n;++i){
read(a[i]);
check(a[i]<=n);
++b[a[i]];
}
sort(a+1,a+n+1);
int s=a[n];
if(!(s&1)){
check(a[1]==s>>1);
check(b[s>>1]==1);
int x=0;
for(int i=s;i>s>>1;--i)check(b[i]>1);
write("Possible\n");
}
else{
int t=(s+1)>>1;
check(a[1]==t);
check(b[t]==2);
int x=0;
for(int i=s;i>t;--i)check(b[i]>1);
write("Possible\n");
}
return 0;
}D
/*
Author: QAQ-Automaton
LANG: C++
PROG: d.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>ll dcmp(T a,T b){return a>b;}
template<ll *a>ll cmp_a(ll x,ll y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const ll SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; ll f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// prll the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed lleger
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// prll a signed lleger
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
const ll p=924844033;
ll f[4047][4047][2],dp[2047],ndp[2047],fac[2047];
int main(){
#ifdef QAQAutoMaton
freopen("d.in","r",stdin);
freopen("d.out","w",stdout);
#endif
ll n,k;
read(n,k);
f[0][0][0]=f[0][0][1]=1;
for(ll i=1;i<=n;++i){
f[i][0][0]=f[i][0][1]=1;
for(ll j=1;j<=i;++j){
f[i][j][0]=f[i-1][j][1];
f[i][j][1]=(f[i-1][j-1][0]+f[i][j][0])%p;
}
}
dp[0]=1;
for(ll i=1;i<=k;++i){
ll m=(n-i)/k;
for(ll j=0;j<=m;++j){
for(ll k=j;k<=n;++k){
ndp[k]=(ndp[k]+dp[k-j]*f[m][j][1])%p;
}
}
for(ll k=0;k<=n;++k){dp[k]=ndp[k];ndp[k]=0;}
for(ll j=0;j<=m;++j){
for(ll k=j;k<=n;++k){
ndp[k]=(ndp[k]+dp[k-j]*f[m][j][1])%p;
}
}
for(ll k=0;k<=n;++k){dp[k]=ndp[k];ndp[k]=0;}
}
//for(ll i=0;i<=n;++i)write(dp[i],i==n?'\n':' ');
fac[0]=fac[1]=1;
for(ll i=2;i<=n;++i)fac[i]=fac[i-1]*i%p;
ll ans=0;
for(ll i=0;i<=n;++i){
ans=(ans+fac[n-i]*dp[i]%p*(i&1?p-1:1))%p;
}
write(ans,'\n');
return 0;
}E
/*
Author: QAQ-Automaton
LANG: C++
PROG: e.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__) #define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// print a signed integer
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
int n,x,y;
vector<int> R[200005],B[200005];
int loop[200005],dfn[200005],low[200005],t,dis[200005],fa[200005],Dis[200005],Fa[200005];
void BlueDFS(int x,int f){
fa[x]=f;
dfn[x]=++t;
dis[x]=dis[f]+1;
for(auto i:B[x])if(i!=f)BlueDFS(i,x);
low[x]=++t;
}
int chk(int x,int y){
if(dfn[x]>dfn[y])swap(x,y);
if(dfn[x]<=dfn[y] && low[y]<=low[x])return dis[y]-dis[x]>2;
return fa[x]!=fa[y];
}
int q[200005],*l,*r;
int RedBFS(int x){
*(l=r=q)=x;
int ans=dis[x]<<1;
if(loop[x])return -1;
while(l<=r){
for(auto i:R[*l])if(i!=Fa[*l]){
Fa[i]=*l;
Dis[i]=Dis[*l]+1;
if(Dis[i]>dis[i])continue;
else chkmax(ans,dis[i]<<1);
if(Dis[i]<dis[i]){
*(++r)=i;
if(loop[i])return -1;
}
}
++l;
}
return ans;
}
int main(){
#ifdef QAQAutoMaton
freopen("e.in","r",stdin);
freopen("e.out","w",stdout);
#endif
read(n,x,y);
if(x==y){write("0\n");return 0;}
int u,v;
for(int i=1;i<n;++i){read(u,v);R[u].push_back(v);R[v].push_back(u);}
for(int i=1;i<n;++i){read(u,v);B[u].push_back(v);B[v].push_back(u);}
dis[0]=-1;
BlueDFS(y,0);
for(int i=1;i<=n;++i){
for(auto j:R[i]){
if(chk(i,j)){loop[i]=1;break;}
}
}
write(RedBFS(x),'\n');
return 0;
}F
/*
Author: QAQ-Automaton
LANG: C++
PROG: f.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>ll dcmp(T a,T b){return a>b;}
template<ll *a>ll cmp_a(ll x,ll y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const ll SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; ll f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// prll the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed lleger
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// prll a signed lleger
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
const ll p=924844033,g=5,ig=554906420;
ll fac[200005],inv[200005],invf[200005],rev[524299];
ll n,u,v;
vector<ll> son[200005];
ll a[524299],b[524299],siz[200005];
void dfs(ll x,ll fa){
siz[x]=1;
for(auto i:son[x])if(i!=fa){dfs(i,x);siz[x]+=siz[i];}
if(fa){
++a[siz[x]];
++a[n-siz[x]];
}
}
ll fpm(ll a,ll b){ll c=1;for(;b;b>>=1,a=a*a%p)if(b&1)c=c*a%p;return c;}
void NTT(ll *a,ll n,ll flg){
for(ll i=1;i<n;++i){
rev[i]=rev[i>>1]>>1 | ((i&1)*(n/2));
if(i<rev[i])swap(a[i],a[rev[i]]);
}
for(ll i=1;i<n;i<<=1){
ll w=fpm(flg==1?g:ig,(p-1)/i/2),ww,u,v;
for(ll j=0;j<n;j+=i+i){
ww=1;
for(ll k=0;k<i;++k){
u=a[j+k];
v=a[j+k+i]*ww%p;
a[j+k]=(u+v)%p;
a[j+k+i]=(u+p-v)%p;
ww=ww*w%p;
}
}
}
if(flg==-1){
ll fg=fpm(n,p-2);
for(ll i=0;i<n;++i)a[i]=a[i]*fg%p;
}
}
int main(){
#ifdef QAQAutoMaton
freopen("f.in","r",stdin);
freopen("f.out","w",stdout);
#endif
read(n);
fac[0]=fac[1]=1;
inv[1]=1;
invf[0]=invf[1]=1;
for(ll i=2;i<=n;++i){
fac[i]=fac[i-1]*i%p;
inv[i]=(p-p/i)*inv[p%i]%p;
invf[i]=invf[i-1]*inv[i]%p;
}
for(ll i=1;i<n;++i){
read(u,v);
son[u].push_back(v);
son[v].push_back(u);
}
dfs(1,0);
for(ll i=0;i<=n;++i){
a[i]=a[i]*fac[i]%p;
b[i]=invf[n-i];
}
ll N=1;
for(;N<=n+n;N<<=1);
NTT(a,N,1);
NTT(b,N,1);
for(ll i=0;i<N;++i)a[i]=a[i]*b[i]%p;
NTT(a,N,-1);
for(ll i=1;i<=n;++i){
write((p-a[i+n]*invf[i]%p+n*fac[n]%p*invf[n-i]%p*invf[i])%p,'\n');
}
return 0;
}