結果

問題 No.3206 う　し　た　ウ　ニ　木　あ　く　ん　笑
ユーザー GOTKAKO
提出日時 2025-07-18 22:13:18
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 245 ms / 3,000 ms
コード長 2,811 bytes
コンパイル時間 1,983 ms
コンパイル使用メモリ 207,164 KB
実行使用メモリ 94,556 KB
最終ジャッジ日時 2025-07-18 22:13:27
合計ジャッジ時間 5,863 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template<typename T> 
class Cumulative{ //1次元.
    private:
    T op(T a,T b){return max(a,b);}
    T inv(T a){return -a;} //ない場合はスルー->rangeans使用不可.
    T e(){return 0;}
    int n;
    vector<T> L,R;
    public:
    Cumulative(){}
    Cumulative(vector<T> &A){make(A);}
    void make(vector<T> &A){
        L = A,R = A;
        n = A.size();
        for(int i=1; i<n; i++) L.at(i) = op(L.at(i-1),L.at(i));
        for(int i=n-2; i>=0; i--) R.at(i) = op(R.at(i),R.at(i+1));
    }
    T rangeans(int l,int r){ //[l,r]だよL<0も許容 逆元はいる.
        if(l > r || r < 0) return e();
        T ret = L.at(r);
        if(l > 0) ret = op(ret,inv(L.at(l-1)));
        return ret;
    }
    T skipone(int pos){ //0<=pos<n;
        T ret = e();
        if(pos > 0) ret = L.at(pos-1);
        if(pos != n-1) ret = op(ret,R.at(pos+1));
        return ret;
    }
    T skiprange(int l,int r){//l<=r.
        T ret = e();
        if(l > 0) ret = L.at(l-1);
        if(r != n-1) ret = op(ret,R.at(r+1));
        return ret;
    }
    T get(int pos){return L.at(pos);}
    vector<T> allA(){return L;}
};

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

    int N; cin >> N;
    vector<vector<int>> Graph(N);
    for(int i=0; i<N-1; i++){
        int u,v; cin >> u >> v;
        u--; v--;
        Graph.at(u).push_back(v);
        Graph.at(v).push_back(u);
    }

    vector<int> par(N,-1);
    vector<vector<int>> kid(N);
    {
        auto dfs = [&](auto dfs,int pos,int back) -> int {
            int ret = 0;
            for(int i=0; i<Graph.at(pos).size(); i++){
                int to = Graph.at(pos).at(i);
                if(to == back){
                    kid.at(pos).push_back(-1);
                    par.at(pos) = i;
                }
                else{  
                    int k = dfs(dfs,to,pos);
                    kid.at(pos).push_back(k);
                    ret = max(ret,k);
                }
            }
            return ret+1;
        };
        dfs(dfs,0,-1);
    }
    int answer = 1;
    {
        auto dfs = [&](auto dfs,int pos,int back,int take) -> void {
            if(back != -1) kid.at(pos).at(par.at(pos)) = take;
            auto S = kid.at(pos);
            sort(S.rbegin(),S.rend());
            for(int i=0; i<S.size(); i++){
                int v = S.at(i);
                answer = max(answer,v*(i+1)+1);
            }

            Cumulative Z(kid.at(pos));
            for(int i=0; i<Graph.at(pos).size(); i++){
                int to = Graph.at(pos).at(i);
                if(to == back) continue;
                int give = Z.skipone(i);
                dfs(dfs,to,pos,give+1);
            }
        };
        dfs(dfs,0,-1,-1);
    }
    cout << answer << endl;
}
0