Submission #1482122

---

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;

bool win[MAX];

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

struct UF{
	vector<int> belong;
	vector<int> size;
	void resize(int n){
		belong.assign(n + 1, -1);
		size.assign(n + 1, 1);
	}
	inline int root(int b){
		if (belong[b] == -1){
			return b;
		}
		belong[b] = root(belong[b]);
		return belong[b];
	}
	void merge(int a, int b){
		a = root(a);
		b = root(b);
		if (a == b)return;
		belong[a] = b;
		size[b] += size[a];
	}
};
UF uf;

int main(){
	cin >> n;
	uf.resize(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);
				uf.merge(i, ll);
				uf.merge(j, ll);
			}
		}
	}
	sigmaL.init(sigma, y);
	for (int i = 0; i < n; i++){
		if (win[i]){
			int a = x;
			int b = i;
			if (uf.root(a)!=uf.root(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;
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++){
		if (win[i] == false){
			int a = x;
			int b = i;
			if (uf.root(a)!= uf.root(b) ){
				continue;
			}
			int lc = sugimL.lca(a, b);
			int tim = sigmaL.dist(a, lc);
			int tim2 = sugimL.dist(lc, y);
			int cost = sigmaL.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:141: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:149: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