Traffic Tree

main.cpp

#include <bits/stdc++.h>
#define REP(i, n) for(int i=0; i < (int)(n); i++)
using namespace std;

typedef long long ll; // -9,223,372,036,854,775,808 から 9,223,372,036,854,775,807

template <class T> using vec = std::vector<T>;
template <class T> using vec2 = vec<vec<T>>;
template <class T> using vec3 = vec<vec<vec<T>>>;

// #define DEBUG

struct Edge{
    int to;
    ll d;
};


vec2<Edge> edges;

vec2<Edge> partials;  // partials[i]はiからEdge.to向きの部分木の部分解

// upを上方として、downにmaxをとる。その木の最大距離をかえす。
ll fillFirst(int up, int down){
    for(auto iter: edges.at(down)){
        if(iter.to == up){
            continue;
        }
        partials.at(down).push_back(Edge{iter.to, iter.d + fillFirst(down, iter.to)});
    }
    sort(partials.at(down).begin(), partials.at(down).end(), [](Edge a, Edge b){return a.d > b.d;});  // aがbより先頭にくるときtrueになるように。これだと大きいほうが先頭。

    return (partials.at(down).empty() ? 0 : partials.at(down).at(0).d);
}

ll getDist(int from, int to){
    for(auto iter: edges.at(from)){
        if(iter.to == to){
            return iter.d;
        }
    }
}

// fillFirstだと子どもから親への部分木の情報がないのでそれを埋める
void fillHoles(int up, int down){
    // downからupへの距離を追加する
    if(up != -1){
        // upでの(down向きを除いた)部分木たちの最大値をもとめる。
        auto current_max = (partials.at(up).empty() ? Edge{-1, 0} : partials.at(up).at(0));
        if(current_max.to == down){
            // 普通に求めた最大値がdown向きだったので2番目の最大値をとる
            current_max = (partials.at(up).size() <= 1 ? Edge{-1, 0} : partials.at(up).at(1));
        }

        partials.at(down).push_back(Edge{up, getDist(down, up) + current_max.d});
        sort(partials.at(down).begin(), partials.at(down).end(), [](Edge a, Edge b){return a.d > b.d;});
    }

    // 下に伝播
    for(auto iter: edges.at(down)){
        if(iter.to == up){
            continue;
        }
        fillHoles(down, iter.to);
    }
}

partials = vec2<Edge>(Nnode);
fillFirst(-1, 0);
fillHoles(-1, 0);


int main(){
    int Nnode;
    cin >> Nnode;
    
    ll totalLen = 0;
    edges = vec2<Edge>(Nnode);
    for(int i=0; i < Nnode - 1; i++){
        int from, to;
        cin >> from >> to;
        from--;
        to--;
        totalLen += 1;
        edges[from].push_back(Edge{to, 1});
        edges[to].push_back(Edge{from, 1});
    }

    // solve
    // solve
    partials = vec2<Edge>(Nnode);
    fillFirst(-1, 0);
    fillHoles(-1, 0);


    for(int i=0; i < Nnode; i++){
        cout << 2*totalLen - partials.at(i).at(0).d << endl;
    }

    return 0;
}