Submission #3607824

---

Source Code Expand

#include<map>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<string>
#include<chrono>
#include<stack>
#include<fstream>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define SIZE(a) ll(a.size())
#define vll vector<ll> 
#define MEMSET(a, n, m) for(ll i=0;i<=n;i++) a[i] = m
#define BIT(n) (ll(1)<<n)
#define UNIQUE(v) v.erase(unique(v.begin(),v.end()),v.end()) 
#define UNIQUE_ARRAY(a,n) n = unique(a + 1, a + x + 1) - a - 1
#define SORT(a,n) sort(a+1,a+n+1)
#define SORT_O(a,n,order) sort(a+1,a+n+1,order)
#define PER(i,y,x) for(ll i=y;i>=x;i--)
typedef long long ll;
using namespace std;

/*
struct point
{
long long dist; long long name;
bool operator<(const point& rhs) const {
return dist > rhs.dist;
}
};
*/
ll const MAX = 300005;
vll edge[MAX];
ll parent[MAX];
ll n;
ll tour[MAX];
ll root;
ll color[MAX] = {};
ll rk[MAX];
ll tour_ord[MAX];

bool ord(ll x, ll y) {
	return tour_ord[x] < tour_ord[y];
}

void dfs() {
	stack<ll> st;
	st.push(1);
	rk[1] = 0;
	parent[1] = 1;
	ll cnt = 1;
	while (!st.empty()) {
		ll cur = st.top();
		if (color[cur] == 0) {
			color[cur] = 1;
			tour[cnt] = cur;
			cnt++;
			REP(i, 0, edge[cur].size()-1) {
				ll next = edge[cur][i];
				if (color[next] == 0) {
					st.push(next);
					rk[next] = rk[cur] + 1;
					parent[next] = cur;
				}
			}
		}
		else {
			st.pop();
			color[cur] = 2;
		}
	}
	REP(i, 1, n) {
		tour_ord[tour[i]] = i;
	}
}

ll parents[MAX][105];

void init() {
	REP(i, 1, n) {
		parents[i][0] = parent[i];
	}
	REP(i, 1, 50) {
		REP(j, 1, n) {
			parents[j][i] = parents[parents[j][i - 1]][i - 1];
		}
	}
}

ll getanc(ll x, ll t) {
	ll bit = 0;
	while (t > 0) {
		if (t&BIT(bit)) {
			t ^= BIT(bit);
			x = parents[x][bit];
		}	
		bit++;
	}
	return x;
}

ll lca(ll x, ll y) {
	if (x == y) return x;
	if (rk[x] < rk[y]) swap(x, y);
	ll t = rk[x] - rk[y];
	x = getanc(x, t);
	if (x == y) return x;
	ll bit = 0;
	while (BIT(bit) <= rk[x]) {
		bit++;
	}
	while (bit >= 0) {
		if (parents[x][bit] != parents[y][bit]) {
			x = parents[x][bit]; y = parents[y][bit];
		}
		bit--;
	}
	return parent[x];
}

int main(){
	cin >> n;
	REP(i, 1, n-1) {
		ll a, b;
		cin >> a >> b;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
	dfs();
	init();
	//REP(i, 1, n) cout << tour[i] << " ";
	//cout << endl;
	ll qqq; cin >> qqq;
	REP(iii, 1, qqq) {
		ll m, k;
		cin >> m >> k;
		ll ans = -1e9;
		vll v;
		REP(i, 1, m) {
			ll t; cin >> t;
			v.push_back(t);
		}
		sort(v.begin(), v.end(), ord);
		for (ll i = 0; i + k - 1 < v.size(); i++) {
			ll j = i + k - 1;
			ll u = lca(v[i], v[j]);
			//cout << "!" << u << endl;
			ans = max(ans, rk[u]);
			//cout << v[i] << " " << v[j] << " " << u << endl;
		}
		cout << ans << endl;
	}
}

Submission Info

Judge Result