FJUTOJ 교전J 10회 원래 이 모든 게 사실이었어(나무확률dp)

제목:
n개의 점으로 구성된 나무, 잎 노드가 문이고 문이 지키는 확률은 이 점의 번호/n이다. 만약에 한 점이 연결된 문의 수위 개수나 길목의 수위 개수가 기수라면 이 점에 수위를 설치해야 한다. 0을 물어보면 나무 뿌리가 지키는 확률이 없다.
문제 풀이:
dp[u]는 나무 위의 노드 u가 수위할 확률이 있음을 나타낸다. 특정한 점 u와 아들 v, dp[u]=(1-dp[u])*dp[v]+dp[u]*(1-dp[v])에 대해 dp[u]는 v라는 아들까지 수위가 홀수일 확률(즉 이 점에 수위가 있을 확률)을 나타낼 수 있다. 그러면 1-dp[u]는 수위가 짝수일 확률을 나타낸다. 그래서 다음 아들과 이 공식을 계속 이용할 수 있다(1-dpu]=[dpu]+dpu][v]][dpu]]][dpu]][dpu]]][dpu]]][dpu]를 나타낼 수 있다.

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define B(x) (1<<(x))
using namespace std;
typedef long long ll;
void cmax(int& a,int b){ if(b>a)a=b; }
void cmin(int& a,int b){ if(b<a)a=b; }
void cmax(ll& a,ll b){ if(b>a)a=b; }
void cmin(ll& a,ll b){ if(b<a)a=b; }
void add(int& a,int b,int mod){ a=(a+b)%mod; }
void add(ll& a,ll b,ll mod){ a=(a+b)%mod; }
const int oo=0x3f3f3f3f;
const ll MOD=100000007;
double dp[100005];
struct EDGE{
    int u,v,next;
}E[200005];
int head[100005],tol;
int n;
 
void Init(){
    memset(head,-1,sizeof head);
    tol=0;
}
 
void add_edge(int u,int v){
    E[tol].v=v;
    E[tol].next=head[u];
    head[u]=tol++;
}
 
void tree_dp(int u,int pre){
    dp[u]=0.0;
    int f=0;
    for(int i=head[u];i!=-1;i=E[i].next){
        int v=E[i].v;
        if(v==pre)continue;
        f=1;
        tree_dp(v,u);
        dp[u]=dp[u]*(1.0-dp[v])+(1.0-dp[u])*dp[v];
    }
    if(!f) dp[u]=1.0-1.0*u/n;
}
 
int main(){
    int T,u,v;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        Init();
        for(int i=1;i<n;i++){
            scanf("%d %d",&u,&v);
            add_edge(u,v);
            add_edge(v,u);
        }
        tree_dp(0,-1);
        printf("%.6lf
",1.0-dp[0]);
    }
    return 0;
}