結果

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

ソースコード

diff # 

/**
	author:  shobonvip
	created: 2025.06.27 21:35:34
**/


#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")


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


typedef long long ll;

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

template <typename T> bool chmin(T &a, const T &b) {
	if (a <= b) return false;
	a = b;
	return true;
}

template <typename T> bool chmax(T &a, const T &b) {
	if (a >= b) return false;
	a = b;
	return true;
}

template <typename T> T max(vector<T> &a){
	assert(!a.empty());
	T ret = a[0];
	for (int i=0; i<(int)a.size(); i++) chmax(ret, a[i]);
	return ret;
}

template <typename T> T min(vector<T> &a){
	assert(!a.empty());
	T ret = a[0];
	for (int i=0; i<(int)a.size(); i++) chmin(ret, a[i]);
	return ret;
}

template <typename T> T sum(vector<T> &a){
	T ret = 0;
	for (int i=0; i<(int)a.size(); i++) ret += a[i];
	return ret;
}

typedef unsigned long long ull;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n; cin >> n;
	vector<int> u(n-1), v(n-1), x(n-1), y(n-1);
	vector ikeru1(n, vector<int>(0));
	vector ikeru2(n, vector<int>(0));

	rep(i,0,n-1) {
		cin >> u[i] >> v[i];
		u[i]--; v[i]--;
		ikeru1[u[i]].push_back(v[i]);
		ikeru1[v[i]].push_back(u[i]);
	}
	rep(i,0,n-1) {
		cin >> x[i] >> y[i];
		x[i]--; y[i]--;
		ikeru2[x[i]].push_back(y[i]);
		ikeru2[y[i]].push_back(x[i]);
	}

	vector<ull> d1(n),d2(n);
	ull ans=0;
	vector<int> tour1, tour2;
	vector<int> first1(n), first2(n);

	auto dfs=[&](auto self, int i, int p, vector<vector<int>> &ikeru, vector<ull> &d, vector<int> &tour, vector<int> &first) -> void {

		first[i] = (int)tour.size();
		tour.push_back(i);
		for (int j: ikeru[i]) {
			if (j == p) continue;
			d[j] = d[i] + 1;
			self(self, j, i, ikeru, d, tour, first);
			tour.push_back(i);
		}

		
	};

	dfs(dfs, 0, -1, ikeru1, d1, tour1, first1);
	dfs(dfs, 0, -1, ikeru2, d2, tour2, first2);
	

	int m = (int)tour1.size();
	assert(m == 2*n-1);
	assert(m == (int)tour2.size());
	
	rep(i,0,m) {
		tour1.push_back(tour1[i]);
		tour2.push_back(tour2[i]);
	}

	vector<bool> seen(n);
	rep(st,0,n){
		{
			fill(all(seen),false);
			seen[st] = 1;
			d1[st] = 0;
			rep(i,first1[st]+1,first1[st]+2*n-1) {
				if (!seen[tour1[i]]) {
					seen[tour1[i]] = 1;
					d1[tour1[i]] = d1[tour1[i-1]] + 1;
				}
			}
		}
		{
			fill(all(seen),false);
			seen[st] = 1;
			d2[st] = 0;
			rep(i,first2[st]+1,first2[st]+2*n-1) {
				if (!seen[tour2[i]]) {
					seen[tour2[i]] = 1;
					d2[tour2[i]] = d2[tour2[i-1]] + 1;
				}
			}
		}
		rep(i,st+1,n){
			ans += d1[i] * d2[i];
		}
	}
	
	ans *= 2;
	cout << ans << '\n';

	


	

}
0