結果

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

ソースコード

diff # 

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

const int n = 400000,Log = 10;
int check[n+1],Second[n];
pair<int,int> table[19][n/Log];
pair<int,int> Group[512][10][10];
pair<int,int> Add[n/Log+1];
int belong[n/Log+1];

int check2[n+1],Second2[n];
pair<int,int> table2[19][n/Log];
pair<int,int> Group2[512][10][10];
pair<int,int> Add2[n/Log+1];
int belong2[n/Log+1];

class SpecialSparseTable{ //LCA専用.
    private:
    int spos = 0,apos = 0,bpos = 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};}
    void maketable(const vector<pair<int,int>> &A){
        int p2 = 1,l = 0,n = A.size();
        for(int i=1; i<=n; i++){
            if(i == p2) check[i] = l,p2 <<= 1,l++;
            else check[i] = check[i-1];
        }
        for(int i=0; i<n; i++) table[0][i] = A[i];
        l = 1;
        for(int i=2; i<=n; i<<=1,l++){
            for(int k=0; k<=n-i; k++) table[l][k] = op(table[l-1][k],table[l-1][k+(i>>1)]);
        }
    }
    void makeGroup(const vector<pair<int,int>> &A){
        int n = A.size();
        const int loop = 1<<(Log-1);
        for(int i=0; i<loop; i++){
            vector<int> now(1);
            for(int k=0; k<Log-1; k++){
                if(i&(1<<k)) now.emplace_back(now.back()+1);
                else now.emplace_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[i][l][r] = {mina,pos};
                }
            }
        }
    }
    pair<int,int> tablerange(int l,int r){//[L,R)だよ.
        int len = r-l,pos = check[len];
        return op(table[pos][l],table[pos][r-(1<<pos)]);
    }
    public:
    void make(const vector<pair<int,int>> &A){
        int n = A.size();
        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[spos] = A.at(k).second,spos++;
                if(now > A.at(k)) now = {A.at(k).first,k};
            }
            Add[apos] = {A.at(i).first,i},apos++;
            belong[bpos] = g,bpos++;
            sepa.push_back(now);
        }
        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[mind.second];
    }
};
int dist[200000],in[200000];
class LCA{
    private:
    SpecialSparseTable ST;
    public:
    void make3(vector<vector<int>> &Graph,int root){ //直接グラフを渡す.
        int t = 0,dep = 0,n = Graph.size(),pos = root;
        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[pos] = t;
            int to = P.at(pos);
            if(Itr.at(pos) == Graph.at(pos).size()) 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()) t++;
                    else to = Graph.at(pos).at(Itr.at(pos));
                }
            }
            if(to != P.at(pos)) dist[to] = dist[pos]+1,P.at(to) = pos,t++,dep++;
            else dep--;
            pos = to;
        }
        ST.make(depth);
    }
    int twodist(int u,int v){
        int tu = in[u],tv = in[v];
        if(tu > tv) swap(tu,tv);
        int lca = ST.rangeans(tu,tv+1);
        return dist[u]+dist[v]-(dist[lca]<<1);
    }
};

class SpecialSparseTable2{ //LCA専用.
    private:
    int spos = 0,apos = 0,bpos = 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};}
    void maketable(const vector<pair<int,int>> &A){
        int p2 = 1,l = 0,n = A.size();
        for(int i=1; i<=n; i++){
            if(i == p2) check2[i] = l,p2 <<= 1,l++;
            else check2[i] = check2[i-1];
        }
        for(int i=0; i<n; i++) table2[0][i] = A[i];
        l = 1;
        for(int i=2; i<=n; i<<=1,l++){
            for(int k=0; k<=n-i; k++) table2[l][k] = op(table2[l-1][k],table2[l-1][k+(i>>1)]);
        }
    }
    void makeGroup(const vector<pair<int,int>> &A){
        const int loop = 1<<(Log-1),n = A.size();
        for(int i=0; i<loop; i++){
            vector<int> now(1);
            for(int k=0; k<Log-1; k++){
                if(i&(1<<k)) now.emplace_back(now.back()+1);
                else now.emplace_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;
                    Group2[i][l][r] = {mina,pos};
                }
            }
        }
    }
    pair<int,int> tablerange(int l,int r){//[L,R)だよ.
        int len = r-l,pos = check2[len];
        return op(table2[pos][l],table2[pos][r-(1<<pos)]);
    }
    public:
    void make(const vector<pair<int,int>> &A){
        int n = A.size();
        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));
                Second2[spos] = A.at(k).second,spos++;
                if(now > A.at(k)) now = {A.at(k).first,k};
            }
            Add2[apos] = {A.at(i).first,i},apos++;
            belong2[bpos] = g,bpos++;
            sepa.push_back(now);
        }
        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(Group2[belong2[r2]][l%Log][(r-1)%Log],Add2[r2]);
        else{
            if(l2 < r2) mind = tablerange(l2,r2);
            if(l%Log) mind = min(mind,add(Group2[belong2[l2-1]][l%Log][Log-1],Add2[l2-1]));
            if(r%Log) mind = min(mind,add(Group2[belong2[r2]][0][(r-1)%Log],Add2[r2]));
        }
        return Second2[mind.second];
    }
};
int dist2[200000],in2[200000];
class LCA2{
    private:
    SpecialSparseTable2 ST;
    public:
    void make3(const vector<vector<int>> &Graph,int root){ //直接グラフを渡す.
        int t = 0,dep = 0,pos = root;
        const int n = 200000;
        vector<pair<int,int>> depth;
        vector<int> Itr(n,-1),P(n,-1);
        while(pos != -1){
            depth.emplace_back(pair{dep,pos});
            if(++Itr.at(pos) == 0) in2[pos] = t;
            int to = P.at(pos);
            if(Itr.at(pos) == Graph.at(pos).size()) 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()) t++;
                    else to = Graph.at(pos).at(Itr.at(pos));
                }
            }
            if(to != P.at(pos)) dist2[to] = dist2[pos]+1,P.at(to) = pos,t++,dep++;
            else dep--;
            pos = to;
        }
        ST.make(depth);
    }
    int twodist(int u,int v){
        int tu = in2[u],tv = in2[v];
        if(tu > tv) swap(tu,tv);
        int lca = ST.rangeans(tu,tv+1);
        return dist2[u]+dist2[v]-(dist2[lca]<<1);
    }
};


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; L1.make3(Graph,0);
    LCA2 L2; L2.make3(Graph2,0);

    ull answer = 0;
    for(int i=0; i<N; i++) for(int k=i+1; k<N; k++){
        ull one = L1.twodist(i,k),two = L2.twodist(i,k);
        answer += one*two;
    }
    answer *= 2;
    cout << answer << endl;
}
0