[Codeforces] 2028E. Alice's Adventures in the Rabbit Hole

https://codeforces.com/contest/2028/problem/E

 

Ob 1. 마녀는 Alice가 위치한 정점의 자식 정점들 중에서 minimum depth가 가장 작은 서브트리를 갖는 곳으로 이동시키는 것이 최적이다.

Ob 2. Alice는 무조건 윗방향으로 뒤도 안 돌아보고 올라가는 것이 최적이다.

 

어떤 정점 $x$에서 리프에 닿지 않고 잘~ 움직이다가 정점 $x$에서 처음으로 $\text{par}(x)$에 이동시키는 확률을 생각하자.

이 확률은 오로지 $x$의 서브트리의 구조에 의해서만 결정되므로 계산하기 쉬울 것으로 기대된다.

 

정확히는, $x$의 minimum depth에 의해서만 결정된다. 왜냐하면 마녀의 이동은 무조건 그 방향으로 고정되기 때문이다.

 

그러면 depth에 따른 확률을 빌려오면 그만이다.

$P(x):=$depth가 $x$일때 리프에 닿지 않고 움직이다가 위로 한 칸 처음으로 이동시키는 확률 이라고 정의하자.

그럼 그림과 같이 $P(x-1)$만을 이용해서 $P(x)$를 표현할 수 있게 된다.

 

즉, $P(x)=\frac 12 \left ( 1 + \frac{P(x-1)}2 + \left (\frac{P(x-1)}2\right )^2 + \cdots  \right )$꼴로 표현된다.

이 식을 잘 정리하면 $P(x)=\frac 1{2-P(x-1)}$이라는 점화식을 얻을 수 있다.

 

이제 어떤 정점 $x$에서 시작하여 잘 살아남아 $\text{par}(x)$로 올라가는 과정에 대한 분석이 끝났다.

그렇다면 임의의 정점에서 시작해서 루트까지 도달하여 빠져나갈 확률을 어떻게 구할 수 있을까?

 

$\text{dp}(u):=u$에서 시작해서 루트까지 도달하여 빠져나갈 확률 이라고 정의하자.

$x$의 minimum depth를 $mnd(x)$라고 하면, $\text{dp}(u)=\text{dp}(\text{par}(u)) \times P(mnd(u))$가 된다.

 

따라서 첫 번째 dfs에서 $mnd(x)$를 전처리하고, $P(x)$도 적당히 메모이제이션하고, 두 번째 dfs에서 dp 전이를 잘 시켜주면 문제를 풀수 있다.

 

코드

https://codeforces.com/contest/2028/submission/290961777

const ll N = 2e5+3;
ll n, mnd[N];
vi adj[N];
mint dp[N];

mint p(ll x) {
    static bool ready[N]{};
    static mint cache[N]{};
    
    if (x==0) return 0;
    if (x==1) return mint(1)/2;
    
    if (ready[x]) return cache[x];
    ready[x] = true;
    
    return cache[x] = mint(1) / (2-p(x-1));
}

void dfs0(ll s=1, ll e=0) {
    mnd[s]=1e9;
    if (s!=1 && siz(adj[s])==1) { // leaf node
        mnd[s] = 0;
    }
    for (auto u : adj[s]) if (u!=e) {
        dfs0(u,s);
        mup(mnd[s], mnd[u]+1);
    }
}

void dfs(ll s=1, ll e=0) {
    if (s==1) dp[s] = 1;
    else dp[s] = dp[e]*p(mnd[s]);
    for (auto u : adj[s]) if (u!=e) {
        dfs(u,s);
    }
}

void precalc() {}
void solution(size_t tc) {
    cin >> n;
    rep(i,1,n) adj[i].clear();
    rep(i,2,n) {
        ll u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs0();
    dfs();
    rep(i,1,n) {
        cout << dp[i] << ' ';
    }
    cout << '\n';
}