結果

問題 No.3193 Submit Your Solution
ユーザー Today03
提出日時 2025-06-27 21:45:06
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 6,649 bytes
コンパイル時間 4,507 ms
コンパイル使用メモリ 309,876 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-27 21:45:25
合計ジャッジ時間 18,065 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define REP(i, n) for(ll i=0; i<(ll)(n); i++)
#define PER(i, n) for(ll i=(ll)(n)-1; i>=0; i--)

template<typename T> int LB(const vector<T>& v, T x) { return lower_bound(ALL(v),x)-v.begin(); }
template<typename T> int UQ(T& v) { sort(ALL(v)); v.erase(unique(ALL(v)),v.end()); return v.size(); }
template<typename T> bool chmax(T &a, T b) { return a<b ? a=b, true : false; }
template<typename T> bool chmin(T &a, T b) { return a>b ? a=b, true : false; }
template<typename T> using rpriority_queue = priority_queue<T,vector<T>,greater<T>>;
using ll=long long; const int INF=1e9+10; const ll INFL=4e18;
using ld=long double; using lll=__int128_t; using ull=unsigned long long;
using VI=vector<int>; using VVI=vector<VI>; using VL=vector<ll>; using VVL=vector<VL>;
using PL=pair<ll,ll>; using VP=vector<PL>; using WG=vector<vector<pair<int,ll>>>;


#ifdef LOCAL
#include "./debug.hpp"
#else
#define debug(...)
#define print_line
#endif



template<class T>
class MinOp{
public:
  T operator () ( T a , T b ){ return min( a , b ); }
};

// sparse table
// static range semigroup query
// time complexity: <O(n log n), O(1)>
// OpFunc is binary operator: T x T -> T
template<typename T, typename OpFunc>
struct SparseTable{
  OpFunc op;
  int size;
  vector<int> lg;
  vector<vector<T> > table;
  void init( const vector<T> &array, OpFunc opfunc ){
    int n = array.size();
    op = opfunc;

    lg.assign( n + 1 , 0 );
    for( int i = 1; i <= n; i++ ){
      lg[i] = 31 - __builtin_clz( i );
    }

    table.assign( lg[n] + 1, array );
    for( int i = 1; i <= lg[n]; i++ ){
      for( int j = 0; j < n; j++ ){
        if( j + (1<<(i-1)) < n ){
          table[i][j] = op( table[i-1][j] , table[i-1][j+(1<<(i-1))] );
        } else {
          table[i][j] = table[i-1][j];
        }
      }
    }
  }
  T query( int l , int r ){
    assert( l < r );
    return op( table[ lg[r-l] ][l], table[ lg[r-l] ][r-(1<<lg[r-l])] );
  }
};


// plus minus one Range Minimum Query
// time complexity: <O(n), O(1)>
struct PMORMQ{
  vector<int> a;
  SparseTable<pair<int,int>,MinOp<pair<int,int> > > sparse_table;
  vector<vector<vector<int> > > lookup_table;
  vector<int> block_type;
  int block_size, n_block;
  void init( const vector<int> &array ){
    a = array;
    int n = a.size();
    block_size = max( 1, ( 31 - __builtin_clz( n ) ) / 2 );
    while( n % block_size != 0 ){
      a.push_back( a.back() + 1 );
      n++;
    }
    n_block = n / block_size;

    vector<pair<int,int> > b( n_block, make_pair( INT_MAX, INT_MAX ) );
    for( int i = 0; i < n; i++ ){
      b[i/block_size] = min( b[i/block_size], make_pair( a[i], i ) );
    }
    sparse_table.init( b, MinOp<pair<int,int> >() );

    block_type.assign( n_block, 0 );
    for( int i = 0; i < n_block; i++ ){
      int cur = 0;
      for( int j = 0; j < block_size-1; j++ ){
        int ind = i * block_size + j;
        if( a[ind] < a[ind+1] ){
          cur |= 1 << j;
        }
      }
      block_type[i] = cur;
    }

    lookup_table.assign( 1 << (block_size-1), vector<vector<int> >( block_size, vector<int>( block_size+1 ) ) );
    for( int i = 0; i < (1<<(block_size-1)); i++ ){
      for( int j = 0; j < block_size; j++ ){
        int res = 0;
        int cur = 0;
        int pos = j;
        for( int k = j+1; k <= block_size; k++ ){
          lookup_table[i][j][k] = pos;
          if( i & ( 1 << (k-1) ) ){
            cur++;
          } else {
            cur--;
          }
          if( res > cur ){
            pos = k;
            res = cur;
          }
        }
      }
    }
  }
  int query( int l, int r ){ // return position
    assert( l < r );
    int lb = l / block_size;
    int rb = r / block_size;
    if( lb == rb ){
      return lb * block_size + lookup_table[ block_type[lb] ][ l % block_size ][ r % block_size ];
    }
    int pl = lb * block_size + lookup_table[ block_type[lb] ][ l % block_size ][ block_size ];
    int pr = rb * block_size + lookup_table[ block_type[rb] ][0][ r % block_size ];
    int pos = pl;
    if( r % block_size > 0 && a[pl] > a[pr] ){
      pos = pr;
    }
    if( lb + 1 == rb ){
      return pos;
    }
    int sp = sparse_table.query( lb+1, rb ).second;
    if( a[pos] > a[sp] ){
      return sp;
    }
    return pos;
  }
};

// LCA
// time complexity: <O(n), O(1)>
struct LCA{
  int n;
  vector<vector<int> > G;
  PMORMQ rmq;
  int cnt;
  vector<int> depth, id, in;
  void init( int size ){
    n = size;
    G.assign( n, vector<int>( 0 ) );
  }
  void add_edge( int a , int b ){
    G[a].push_back( b );
    G[b].push_back( a );
  }
  void dfs( int x , int p , int d ){
    id[cnt] = x;
    depth.push_back( d );
    in[x] = cnt++;
    for( int v : G[x] ){
      if( v == p ){
        continue;
      }
      dfs( v , x , d+1 );
      id[cnt] = x;
      depth.push_back( d );
      cnt++;
    }
  }
  void precalc( int root ){
    cnt = 0;
    depth.clear();
    in.assign( n, -1 );
    id.assign( 2*n-1, -1 );
    dfs( root, -1, 0 );
    rmq.init( depth );
  }
  int lca( int a , int b ){
    int x = in[a];
    int y = in[b];
    if( x > y ){
      swap( x , y );
    }
    int pos = rmq.query( x, y + 1 );
    return id[pos];
  }
};


/// @brief 重みなしグラフ g の頂点 start からの最短距離を求める
/// @note O(E+V)
vector<ll> BFS(const vector<vector<int>>& g, int start=0) {
    int n=g.size();
    vector<ll> ret(n,INF); ret[start]=0;
    queue<int> que; que.push(start);

    while(!que.empty()) {
        int now=que.front();que.pop();
        for(int nxt:g[now]) if(chmin(ret[nxt],ret[now]+1)) que.push(nxt);
    }

    return ret;
}


//----------------------------------------------------------

void solve() {
    int N; cin>>N;
    VVI G(N), H(N);
    REP(i,N-1) {
        int u,v; cin>>u>>v; u--; v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    REP(i,N-1) {
        int u,v; cin>>u>>v; u--; v--;
        H[u].push_back(v);
        H[v].push_back(u);
    }

    auto d1=BFS(G), d2=BFS(H);
    LCA l1, l2;
    l1.init(N); l2.init(N);
    REP(i,N) for(int j: G[i]) if(i<j) l1.add_edge(i,j);
    REP(i,N) for(int j: H[i]) if(i<j) l2.add_edge(i,j);
    l1.precalc(0); l2.precalc(0);
    debug(d1,d2);

    ull ans=0;
    REP(i,N) REP(j,i) {
        ull dist1=d1[i]+d1[j]-2*d1[l1.lca(i,j)];
        ull dist2=d2[i]+d2[j]-2*d2[l2.lca(i,j)];
        ans+=dist1*dist2;
        debug(i,j,l1.lca(i,j),l2.lca(i,j));
    }
    cout<<ans*2<<'\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cout<<fixed<<setprecision(15);
    int T=1;
    //cin>>T;
    while(T--) solve();
}
0