Submission #1482101

---

Source Code Expand

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

struct LCA{
	vector<vector<int> > g;
	const int MAX_LOG = 22;
	vector<vector<int> > lcc;
	vector<int> dep;
	vector<int> myr;
private:
	void init2(){
		int n = g.size();
		for (int i = 0; i + 1 < MAX_LOG; i++){
			for (int j = 0; j < n; j++){
				if (lcc[i][j] == -1){
					lcc[i + 1][j] = -1;
					continue;
				}
				lcc[i + 1][j] = lcc[i][lcc[i][j]];
			}
		}
	}
public:
	int lca(int a, int b){
		if (dep[a] < dep[b]){
			swap(a, b);
		}
		for (int i = 0; i < MAX_LOG; i++){
			if (((dep[a] - dep[b]) >> i) & 1){
				a = lcc[i][a];
			}
		}
		if (a == b){
			return a;
		}
		for (int i = MAX_LOG - 1; i >= 0; i--){
			if (lcc[i][a] != lcc[i][b]){
				a = lcc[i][a];
				b = lcc[i][b];
			}
		}
		return lcc[0][a];
	}
private:
	int flag_r;
	inline void dfs(int b, int pr = -1, int d = 0){
		for (auto &i : g[b]){
			if (i == pr)continue;
			dfs(i, b, d + 1);
		}
		dep[b] = d;
		lcc[0][b] = pr;
		myr[b] = flag_r;
	}
public:

	void init(vector<vector<int> > &tree, int root = 0){
		g = tree;
		myr.resize(tree.size(), -1);
		flag_r = root;
		lcc.resize(MAX_LOG, vector<int>(g.size(), 0));
		dep.resize(g.size());
		dfs(root);
		init2();
	}
	void init(vector<vector<int> > &tree, vector<int> &root){
		g = tree;
		myr.resize(tree.size(), -1);
		lcc.resize(MAX_LOG, vector<int>(g.size(), 0));
		dep.resize(g.size());
		for (int &i : root){
			if (myr[i] == -1){
				flag_r = i;
				dfs(i);
			}
		}
		init2();
	}
	int dist(int a, int b){ 
		if (myr[a] != myr[b]){
			return -1;
		}
		int lc = lca(a, b);
		return dep[a] + dep[b] - 2 * dep[lc];
	}
};

#define MAX 200002

int n;

int x;
int y;

vector<vector<int> > sigma;
vector<vector<int> > sugim;

LCA sigmaL;
LCA sugimL;
LCA sigmaLL;

bool win[MAX];

vector<vector<int> > vv;
queue<int> q;
vector<int> ord;
bool vis[MAX];

int main(){
	cin >> n;
	cin >> x >> y;
	sigma.resize(n,vector<int>());
	sugim = sigma; 
	vv = sigma;
	for (int i = 1; i < n; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		a--;
		b--;
		sigma[a].push_back(b);
		sigma[b].push_back(a);
	}
	for (int i = 1; i < n; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		a--;
		b--;
		sugim[a].push_back(b);
		sugim[b].push_back(a);
	}
	x--;
	y--;
	sugimL.init(sugim,y);
	for (int i = 0; i < n; i++){
		for (int &j : sigma[i]){
			if (i > j)continue;
			int d = sugimL.dist(i, j);
			if (d > 2){
				win[i] = true;
				win[j] = true;
				continue;
			}
			else{
				int ll = sugimL.lca(i, j);
				if (ll != i&&ll != j){
					vv[i].push_back(ll);
					vv[ll].push_back(i);
					vv[j].push_back(ll);
					vv[ll].push_back(j);
				}
				else{
					vv[i].push_back(j);
					vv[j].push_back(i);
				}
			}
		}
	}
	vis[y] = true;
	q.push(y);
	while (!q.empty()){
		int b = q.front();
		q.pop();
		for (int &i : sugim[b]){
			if (!vis[i]){
				vis[i] = true;
				q.push(i);
			}
		}
		ord.push_back(b);
	}
	sigmaL.init(vv, ord);
	for (int i = 0; i < n; i++){
		if (win[i]){
			int a = x;
			int b = i;
			if (sigmaL.myr[a] != sigmaL.myr[b]){
				continue;
			}
			int lc = sugimL.lca(a, b);
			int tim = sigmaL.dist(a, lc);
			int tim2 = sugimL.dist(lc, y);
			if (tim == -1){
				continue;
			}
			if (tim < tim2){
				puts("-1");
				return 0;
			}
		}
	}
	sigmaLL.init(sigma, y);
	int ans = 0;
	for (int i = 0; i < n; i++){
		if (win[i] == false){
			int a = x;
			int b = i;
			if (sigmaL.myr[a] != sigmaL.myr[b]){
				continue;
			}
			int lc = sugimL.lca(a, b);
			int tim = sigmaLL.dist(a, lc);
			int tim2 = sugimL.dist(lc, y);
			int cost = sigmaLL.dist(a, b);
			if (tim > tim2){
				continue;
			}
			if (tim == tim2){
				if (b == lc){
					ans = max(ans, cost);
				}
			}
			if (tim < tim2){
				ans = max(ans, cost + tim2 - tim);
			}
		}
	}
	cout << 2*ans << endl;
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:117:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
                        ^
./Main.cpp:125:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
                        ^

Judge Result