結果

問題 No.3193 Submit Your Solution
ユーザー GOTKAKO
提出日時 2025-06-27 21:40:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,762 bytes
コンパイル時間 2,852 ms
コンパイル使用メモリ 223,000 KB
実行使用メモリ 53,544 KB
最終ジャッジ日時 2025-06-27 21:41:10
合計ジャッジ時間 15,395 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

class SpecialSparseTable{ //LCA専用.
    private:
    int log = 0;
    pair<int,int> op(pair<int,int> &a,pair<int,int> &b){return min(a,b);}
    pair<int,int> add(pair<int,int> &a,pair<int,int> &b){return {a.first+b.first,a.second+b.second};}
    vector<int> check,belong,Second;
    vector<pair<int,int>> Add;
    vector<vector<vector<pair<int,int>>>> Group;
    vector<vector<pair<int,int>>> table;
    void maketable(vector<pair<int,int>> &A){
        int n = A.size();
        table.resize(n+1); check.resize(n+1);
        int p2 = 1;
        for(int i=1; i<=n; i++){
            if(i == p2) check.at(i) = i,p2 *= 2;
            else check.at(i) = check.at(i-1);
        }
        table.at(1) = A;
        for(int i=2; i<=n; i*=2){
            table.at(i).resize(n);
            for(int k=0; k<=n-i; k++) table[i][k] = op(table[i>>1][k],table[i>>1][k+(i>>1)]);
        }
    }
    void makeGroup(vector<pair<int,int>> &A){
        int loop = 1<<(log-1);
        Group.resize(loop,vector<vector<pair<int,int>>>(log,vector<pair<int,int>>(log)));
        for(int i=0; i<loop; i++){
            vector<int> now(1);
            for(int k=0; k<log-1; k++){
                if(i&(1<<k)) now.push_back(now.back()+1);
                else now.push_back(now.back()-1);
            }
            for(int l=0; l<log; l++){
                int mina = 1001001001,pos = -1;
                for(int r=l; r<log; r++){
                    if(mina > now.at(r)) mina = now.at(r),pos = r;
                    Group.at(i).at(l).at(r) = {mina,pos};
                }
            }
        }
    }
    pair<int,int> tablerange(int l,int r){//[L,R)だよ.
        int len = r-l,pos = check.at(len);
        return op(table.at(pos).at(l),table.at(pos).at(r-pos));
    }
    public:
    void make(vector<pair<int,int>> &A){
        int p2 = 1,n = A.size();
        while(p2 < n) p2 *= 2,log++;
        log = max(1,(log+1)/2);
 
        vector<pair<int,int>> sepa;
        for(int i=0; i<n; i+=log){
            int r = min(n,i+log),g = 0;
            pair<int,int> now = {1001001001,-1};
            for(int k=i; k<r; k++){
                if(k != r-1 && A.at(k).first+1 == A.at(k+1).first) g += (1<<(k-i));
                Second.push_back(A.at(k).second);
                if(now > A.at(k)) now = {A.at(k).first,k};
            }
            Add.push_back({A.at(i).first,i});
            sepa.push_back(now); belong.push_back(g);
        }
        maketable(sepa); makeGroup(A); 
    }
    int rangeans(int l,int r){ //[l,r)!
        int l2 = (l+log-1)/log,r2 = r/log;
        pair<int,int> mind = {1001001001,-1};
        if(l2 > r2) mind = add(Group[belong[r2]][l%log][(r-1)%log],Add[r2]);
        else{
            if(l2 < r2) mind = tablerange(l2,r2);
            if(l%log) mind = min(mind,add(Group[belong[l2-1]][l%log][log-1],Add[l2-1]));
            if(r%log) mind = min(mind,add(Group[belong[r2]][0][(r-1)%log],Add[r2]));
        }
        return Second.at(mind.second);
    }
};
class LCA{
    private:
    vector<int> dist,in,out;
    SpecialSparseTable ST;
    public:
    void make1(vector<int> &P){// p0=-1でp1以降だけ
        int r = 0;
        vector<vector<int>> G(P.size()+1);
        for(int i=0; i<P.size(); i++) G.at(P.at(i)).push_back(i+1); 
        make3(G,r);
    }
    void make2(vector<int> &P){//pi=-1 iは固定されていない.
        int r = -1;
        vector<vector<int>> G(P.size());
        for(int i=0; i<P.size(); i++){
            if(P.at(i) == -1) r = i;
            else G.at(P.at(i)).push_back(i);
        }
        make3(G,r);
    }
    void make3(vector<vector<int>> &Graph,int root){ //直接グラフを渡す.
        int t = 0,dep = 0,n = Graph.size(),pos = root;
        dist.resize(n),in.resize(n),out.resize(n);
 
        vector<pair<int,int>> depth;
        vector<int> Itr(n,-1),P(n,-1);
        while(pos != -1){
            depth.push_back({dep,pos});
            if(++Itr.at(pos) == 0) in.at(pos) = t;
            int to = P.at(pos);
            if(Itr.at(pos) == Graph.at(pos).size()) out.at(pos) = ++t;
            else{
                to = Graph.at(pos).at(Itr.at(pos));
                if(to == P.at(pos)){
                    Itr.at(pos)++;
                    if(Itr.at(pos) == Graph.at(pos).size()) out.at(pos) = ++t;
                    else to = Graph.at(pos).at(Itr.at(pos));
                }
            }
            if(to != P.at(pos)) dist.at(to) = dist.at(pos)+1,P.at(to) = pos,t++,dep++;
            else dep--;
            pos = to;
        }
        ST.make(depth);
    }
    int lca(int u,int v){
        int tu = in.at(u),tv = in.at(v);
        if(tu > tv) swap(tu,tv);
        return ST.rangeans(tu,tv+1);
    }
    int twodist(int u,int v){return dist.at(u)+dist.at(v)-2*dist.at(lca(u,v));}
    int onedist(int u){return dist.at(u);} 
};

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

    int N; cin >> N;
    vector<vector<int>> Graph(200000),Graph2(200000);
    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);
    }
    for(int i=0; i<N-1; i++){
        int u,v; cin >> u >> v;
        u--; v--;
        Graph2.at(u).push_back(v);
        Graph2.at(v).push_back(u);
    }

    int n = 200000;
    for(int i=N; i<n; i++){
        Graph.at(i-1).push_back(i);
        Graph.at(i).push_back(i-1);
        Graph2.at(i-1).push_back(i);
        Graph2.at(i).push_back(i-1);
    }

    LCA L1,L2; L1.make3(Graph,0),L2.make3(Graph2,0);
    ull answer = 0;
    for(int i=0; i<N; i++) for(int k=i+1; k<N; k++) answer += (ull)L1.twodist(i,k)*L2.twodist(i,k);
    answer *= 2;
    cout << answer << endl;
}
0