Rerooting Techinque on Tree

정의

• Tree에서 Root를 바꿀 때 SubNode의 갯수를 이용해서 문제를 푸는 경우 프로출신들이 아닌 아마추어들은 $O(N^2)$ 으로 모든 node를 Tree의 Root로 정의한 후 문제를 해결하는데 이러면 시간초과에 걸릴 가능성이 매우 크다
• 그래서 Reroging Techinque on Tree를 이용해서 $O(N)$으로 해결해준다.

해결 방법

• 첫번째 dfs에서 Root를 고정한 후 SubNode의 갯수들을 dp해주면서 Root에 대한 SubNode들의 누적합을 구한다.
• 두번째 dfs에서 첫번째 Root에 대해서 Child가 부모 Node로 가고 Parent Node가 Child로 갔을 때의 SubNode들의 누적합을 구해준다. 여기서는 핵심 Techinque이 들어간다.
  • $dp[child] = dp[현재 child Node의 Parent Node] - Sub[child] + 전체 Node의 합 - Sub[child]$
  • 이렇게 되는 이유는 ParentNode가 ChildNode로 갈 때 부모의 Node에 대해서 SubNode의 합은 보존된다. 자식으로간 ParentNode의 SubNode는 RootNode(ParentNode의 ChildNode)에 대한 Edge 길이가 1씩 증가한다.
  • 부모가 된 ChildNode에 대한 SubNode들은 root가 된 childNode에 대해서 edge 길이가 1씩 감소한다

그림

현재 Node의 ChildNode가 Root로 가기때문에 $SubNode[Root]$는 보존된다. 하지만 $SubNode[ChildNode]$ 가 바뀌었고 그렇기 때문에 $SubNode[root]$ 의 값을 전체 Node의 합에서 Root로 올라간 $SubNode[ChildNode]$을 빼준다.

Example CF 1187E

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cmath>
#include <numeric>
#include <limits>
#include <sstream>
#include <iomanip> 

#define INF 0x3f3f3f3f // 경우에 따라 다르게
// long long 일 1e18

using namespace std;

int n ;
vector<int> edge[200001];
int  sub[200001];
int dp[200001];
int result = 0;

void dfs(int v, int parent)
{
    sub[v] = 1; 
    for(auto c : edge[v])
    {
        if(c==parent)
            continue;
        dfs(c,v);
        sub[v] += sub[c] ;
    }

    dp[1] += sub[v];
}

void cal(int v, int parent)
{

    for(auto c :edge[v])
    {
        if(c == parent)
        {   
            continue;
        }

        dp[c] =  dp[v] - sub[c] + n - sub[c];
       
        cal(c,v);

    }


}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n ;

    for(int i = 0 ;  i < n-1; i++)
    {
        int u,v ;
        cin >> u >> v ;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }

    dfs(1,-1);

    cal(1,-1);

    for(int i = 1 ; i <=n; i++)
    {
        cout << dp[i] <<" "; 
    }
    cout <<"\n";
    
    for(int i = 1; i<= n; i++)
    {
        result = max(result , dp[i]);
    }

    cout << result <<"\n";
}

후기

혼자 머리박고 알아내느라 힘들었다.