HDU4661 Message Passing 루트 교체 dp 콤보 수학

HDU4661 Message Passing 스왑 루트 dp

제목의 뜻

나무 한 그루에 모든 점마다 유일무이한 소식이 있다. 매번 한 점으로 하여금 소식을 이웃점에 전달하게 하면 이 이웃점에서 이 소식을 알게 된다.한 점이 전달될 때 그것이 알고 있는 모든 소식을 전달한다.최소 전달 횟수를 충족하는 방안의 종류가 얼마나 되냐고 묻는다.
ps:뿌리를 바꿀 때 바보같이 바뀌었어요. 뒤에서 사내 블로그를 봤는데 간소화할 수 있더라고요.고맙습니다.https://www.cnblogs.com/zhsl/archive/2013/08/10/3250755.html

문제풀이

감성적으로 생각해 보면 그래서 정보를 한 점에 집중하고 가장 좋은 것으로 전해져야 한다. 핸드볼 아래의 예는 매우 옳다. 한 번에 변권과 두 배가 되고 모든 점이 이 중심점을 할 수 있다.그러나 본 문제는 방안수를 구하는 것이다. 우리가 하나의 뿌리 노드를 정하면 모든 합법적인 집중 방안은 유일하게 분산된 방안이 대응하는 것을 알 수 있다. 즉, 그들이 서로 역과정이기 때문에 집중할 수 있는 방안수 = 발산할 수 있는 방안수이다. 그러면 한 집중점에 있어 방안 총수는 집중된 방안수 * 발산할 수 있는 방안 트리이다.이 문제는 모든 점에 대해 한 번씩 요구하기 때문에 dp를 바꾸는 것을 생각하기 어렵지 않다.우리는 먼저 고정점에 대해 어떻게 구하는지 고려한다. 방안 수는 사실 나무의 토폴로지 서수이다.우리는 dp[x]를 x를 뿌리 노드로 하는 방안수로 하고sz[x]는 x자 나무 크기로 한다. 만약에 x노드에 3개의 자 노드 u, v, w가 있다면.우리는 먼저 u, v 두 개의 점이 몇 가지 상황이 있는지 고려하고 밑에서 위로 구한다. 우리는 dp[u], dp[v]가 이미 알고 있다고 가정한다. 그러면 이 두 개의 서브트리를 합친 방안수는\(dp[u]*dp[v]*C(sz[u]+sz[v],sz[v])\)이다. 뒤에 이 조합수는 어떻게 이해합니까?\(C(sz[u]+sz[v],sz[u])\)는 sz[u]+sz[v]의 위치에 해당하고 n개를 선택하여 서브 트리 n에 기입한다. 즉, 모두\(dp[u]\)의 합법적인 토폴로지 서열에 해당한다. 나는\(dp[v]\)개의 토폴로지 서열을 서로 삽입하고 u, v, 서열의 점 추출 순서가 변하지 않는다. w가 많을 때 상황은 다음과 같다. 만약에 우리는 u, v가 합쳐진 서브 트리를 새로운 서브 트리로 볼 수 있다.

\(dp[k]=dp[u]*dp[v]*C(sz[u],sz[v],sz[v])\)를 병합하여\(dp[w]*dp[k]*C(sz[k]+sz[w],sz[w])\)를 대입

\(dp[w]*dp[u]*dp[v]*C(sz[u],sz[v],sz[v])*C(sz[u]+sz[v]+sz[w],sz[w])\)화 간략화

\(\frac{dp[u]*dp[v]*dp[w]*(sz[u]+sz[v]+sz[w])!}{sz[u]!*sz[v]!*sz[w]!}\)

우리는 상술한 공식에서 여러 개의 하위 노드를 얻어낼 때 dp[x]의 계산 공식은

\(dp[x]=\frac{(\prod dp[son])*(sz[x]-1)!}{\prod sz[son]!}\)

이로부터 단번에 구했다.어떻게 뿌리를 바꿉니까?{(n-1)!*dp[x]}\) x를 뿌리로 하는 dp는\(dp[x]=\rac{dp[x]*(n-1)!*t}{(sz[x]-1)!*(n-sz[x])!}\)
대입t득\(dp[x]=\rac{dp[x]*(n-1)!*dp[fa]*sz[x]!*(n-1-sz[x])!}{(sz[x]-1)!*(n-sz[x])!*(n-1)!*dp[x]}\)화 간략화\(dp[x]=\rac{dp[fa]*sz[x]}{(n-sz[x])}\)화 두통은 아래의 두 가지 해법보다 못하다.
해법2: ABC160 F - Distributing Integers를 보면 쓰기가 훨씬 간단해진다.
해법 1코드(2 안 썼어, 그 문제랑 차이가 별로 없어)

#include
using namespace std;
#define pb push_back
#define F first
#define S second
#define mkp make_pair
#define pii pair
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=1e6+10;
const int mod=1e9+7;
int dp[maxn],sz[maxn];
int n;
vectorv[maxn];
ll mul(ll a,ll b){
	return ((a%mod)*(b%mod)+mod)%mod;
}
ll add(ll a,ll b){
	return (a+b+mod)%mod;
}
ll fpow(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1)ans=mul(ans,a);
		a=mul(a,a);
		b>>=1;
	}
	return ans;
}
int fac[maxn],inv[maxn],facinv[maxn];
void pre_fac(int up){
	//  
	fac[0]=fac[1]=1;
	for(int i=2;i<=up;i++)fac[i]=mul(fac[i-1],i);
	//    
	facinv[up]=fpow(fac[up],mod-2);
	for(int i=up-1;i>=0;i--)facinv[i]=mul(facinv[i+1],i+1);
	//     
	inv[1] = 1;
	for(int i = 2; i <=up; ++ i)
    inv[i] = mul((mod - mod / i) , inv[mod % i] );
}

ll C(ll n,ll m){//n>=m
	return mul(facinv[n-m],mul(fac[n],facinv[m]));
}
ll ans=0;

void dfs(int x,int fa){
	dp[x]=sz[x]=1;
	for(auto y:v[x]){
		if(y==fa)continue;
		dfs(y,x);
		sz[x]+=sz[y];
		dp[x]=mul(facinv[sz[y]],mul(dp[x],dp[y]));
	}
	dp[x]=mul(dp[x],fac[sz[x]-1]);
}

void reroot(int x,int fa){
	dp[x]=mul(mul(dp[fa],sz[x]),inv[n-sz[x]]);
	ans=add(ans,mul(dp[x],dp[x]));
	for(auto y:v[x]){
		if(y==fa)continue;
		reroot(y,x);
	}
}
void solve(){
	ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)v[i].clear();
	for(int i=1;i