[noi simulation] juice tree (tree DP)

Topic

The original title is ：「 Cattle guest 31454H」Permutation on Tree

Answer key

We take apart the absolute value symbols
$$\sum _{i=1}^{n-1}|P_{i+1}-P_i|=\sum _{i=1}^{n-1}(P_{i+1}-P_i)[P_{i+1}>P_i]+(P_i-P_{i+1})[P_{i+1}<P_i]$$

Then for each number $x$, Calculate its coefficient as 1 The number and coefficient of schemes are -1 Number of alternatives .

Take the coefficient as 1 For example .

The original number of global schemes is through a simple DP（$dp[x]=(siz[x]-1)!{\prod }_{x\to y}\frac{dp[y]}{siz[y]!}$） Calculated , We should give special consideration to $x$ , Just cut the whole arrangement into two halves , On the tree, it shows as cutting $x$ The subtree of （ Calculate the number of internal schemes of the subtree separately ）, Then select some of the remaining trees and put them in the arrangement $x$ Behind . meanwhile , We have to give $x$ Find a partner Find a neighbor to match . So the design state ：

• $dp0[i][j]$ ： Just consider $i$ Inside the subtree of , Let go of $j$ A to $x$ Behind , Not given $x$ Number of paired schemes .
• $dp1[i][j]$ ： Just consider $i$ Inside the subtree of , Let go of $j$ A to $x$ Behind , The subtree has been given $x$ Number of paired schemes .

When we merge two subtrees $A,B$ when ,
$$\begin{gathered} dp{0}^{\prime }[root][j+k]\leftarrow dp0[A][j]\cdot dp0[B][k]\cdot \left(\genfrac{}{}{0ex}{}{siz[A]+siz[B]}{siz[A]}\right)\cdot \left(\genfrac{}{}{0ex}{}{i+k}{i}\right) \\ dp{1}^{\prime }[root][j+k]\leftarrow dp0[A][j]\cdot dp1[B][k]\cdot \left(\genfrac{}{}{0ex}{}{siz[A]+siz[B]-1}{siz[B]-1}\right)\cdot \left(\genfrac{}{}{0ex}{}{i+k}{i}\right) \\ \leftarrow dp1[A][j]\cdot dp0[B][k]\cdot \left(\genfrac{}{}{0ex}{}{siz[A]+siz[B]-1}{siz[A]-1}\right)\cdot \left(\genfrac{}{}{0ex}{}{i+k}{i}\right) \end{gathered}$$

then , if $i$ No $x$ The ancestors of the , There can be
$$dp0[i][siz[i]]\leftarrow dp0[i][0]$$

if $i$ Than $x$ Small （ And $x$ The coefficient of pairing is 1）, Yes
$$dp1[i][siz[i]-1]\leftarrow dp0[i][0]\cdot ([i=fa[x]\vee lca(i,x)\ne i]+[lca(i,x)\ne i])$$

Finally, consider $x$ The matching of your son .

Total States $O(\sum siz[i])$ , Transfer is a classic tree backpack , So the total time complexity $O(n^3)$ .

CODE

Not very often , There is even a lot of waste code

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<random>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#pragma GCC optimize(2)
using namespace std;
#define MAXN 205
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define PR pair<int,int>
#define UIN unsigned int
int xchar() {
    
	static const int maxn = 1000000;
	static char b[maxn];
	static int pos = 0,len = 0;
	if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
// #define getchar() xchar()
inline LL read() {
    
	LL f = 1,x = 0;int s = getchar();
	while(s < '0' || s > '9') {
    if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
	while(s >= '0' && s <= '9') {
    x = (x<<1) + (x<<3) + (s^48);s = getchar();}
	return f*x;
}
void putpos(LL x) {
    if(!x)return ;putpos(x/10);putchar((x%10)^48);}
inline void putnum(LL x) {
    
	if(!x) {
    putchar('0');return ;}
	if(x<0) putchar('-'),x = -x;
	return putpos(x);
}
inline void AIput(LL x,int c) {
    putnum(x);putchar(c);}

const int MOD = 1000000007;
int n,m,s,o,k;
int rt,C[MAXN<<1][MAXN<<1];
int hd[MAXN],nx[MAXN<<1],v[MAXN<<1],cne;
void ins(int x,int y) {
    
	nx[++ cne] = hd[x]; v[cne] = y; hd[x] = cne;
}
int d[MAXN],fa[MAXN];
void dfs0(int x,int ff) {
    
	d[x] = d[fa[x] = ff] + 1;
	for(int i = hd[x];i;i = nx[i]) {
    
		if(v[i] != ff) {
    
			dfs0(v[i],x);
		}
	}return ;
}
int lca(int a,int b) {
    
	if(d[a] < d[b]) swap(a,b);
	while(d[a] > d[b]) a = fa[a];
	if(a == b) return a;
	while(a != b) a = fa[a],b = fa[b];
	return a;
}
int Ft;
int dp[MAXN][MAXN],dp1[MAXN][MAXN],siz[MAXN];
bool ifa[MAXN],mg[MAXN];
void dfsi(int x,int ff) {
    
	dp[x][0] = 1; siz[x] = 0;
	for(int i = hd[x];i;i = nx[i]) {
    
		int y = v[i]; if(y == ff) continue;
		dfsi(y,x); siz[x] += siz[y];
		dp[x][0] = dp[x][0] *1ll* dp[y][0] % MOD * C[siz[x]][siz[y]] % MOD;
	} siz[x] ++; return ;
}
void dfs(int x,int ff) {
    
	for(int i = 0;i <= n;i ++) dp[x][i] = dp1[x][i] = 0;
	dp[x][0] = 1; siz[x] = 0;
	for(int i = hd[x];i;i = nx[i]) {
    
		int y = v[i]; if(y==ff || y==Ft) continue;
		dfs(y,x); siz[x] += siz[y];
		for(int i = siz[x];i >= 0;i --) {
    
			int dpp = 0,dpp1 = 0;
			for(int j = max(0,siz[y]-(siz[x]-i));j <= siz[y] && j <= i;j ++) {
    
				(dpp += dp[x][i-j]*1ll*dp[y][j]%MOD * C[siz[x]-i][siz[y]-j] % MOD * C[i][j] % MOD) %= MOD;
				if(i<siz[x]) (dpp1 += dp1[x][i-j]*1ll*dp[y][j]%MOD * C[siz[x]-i-1][siz[y]-j] % MOD * C[i][j] % MOD) %= MOD;
				if(i<siz[x] && j<siz[y]) (dpp1 += dp[x][i-j]*1ll*dp1[y][j]%MOD * C[siz[x]-i-1][siz[y]-j-1] % MOD * C[i][j] % MOD) %= MOD;
			}
			dp[x][i] = dpp; dp1[x][i] = dpp1;
		}
	}
	siz[x] ++;
	if(!ifa[x]) dp[x][siz[x]] = dp[x][0];
	if(mg[x] && (!ifa[x] || x == fa[Ft])) (dp1[x][siz[x]-1] += dp[x][0]) %= MOD;
	if(mg[x] && !ifa[x]) (dp1[x][siz[x]-1] += dp[x][0]) %= MOD;
	return ;
}
int solve(int s,int op) {
    
	Ft = s;
	for(int i = 1;i <= n;i ++) {
    
		ifa[i] = mg[i] = 0;
		if(op > 0) mg[i] = (i > s);
		else mg[i] = (i < s);
	}
	int as = 0;
	int p = s; while(p) ifa[p] = 1,p = fa[p];
	dfsi(s,fa[s]);
	int le = siz[s];
	int as0 = 1,as1 = 0,sz = 0;
	for(int i = hd[s];i;i = nx[i]) {
    
		int y = v[i]; if(y == fa[s]) continue;
		sz += siz[y];
		as1 = as1 *1ll* dp[y][0] % MOD * C[sz-1][siz[y]] % MOD;
		if(mg[y]) (as1 += as0 *1ll* dp[y][0] % MOD * C[sz-1][siz[y]-1] % MOD) %= MOD;
		as0 = as0 *1ll* dp[y][0] % MOD * C[sz][siz[y]] % MOD;
	}
	if(rt != s) {
    
		dfs(rt,0);
		for(int i = 0;i <= siz[rt];i ++) {
    
			(as += dp1[rt][i] *1ll* dp[s][0] % MOD * C[le-1+i][i] % MOD) %= MOD;
			if(le>1) (as += dp[rt][i] *1ll* as1 % MOD * C[le-2+i][i] % MOD) %= MOD;
		}
	}
	else as = as1;
	return as;
}
int main() {
    
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	n = read(); rt = read();
	for(int i = 1;i < n;i ++) {
    
		s = read();o = read();
		ins(s,o); ins(o,s);
	}
	dfs0(rt,0);
	C[0][0] = 1;
	for(int i = 1;i <= n;i ++) {
    
		C[i][0] = C[i][i] = 1;
		for(int j = 1;j < i;j ++) {
    
			C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
		}
	}
	int ans = 0;
	for(int i = 1;i <= n;i ++) {
    
		int A = solve(i,-1),B = solve(i,1);
		ans = (ans + (A +MOD- B) *1ll* i) % MOD;
	}
	AIput(ans,'\n');
	return 0;
}