lca 20ptsRE求助
查看原帖
lca 20ptsRE求助
991489
_Memory楼主2024/8/17 17:29
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
const int M = 5e4 + 5;
int head[N], head2[N], cnt, cnt2;
int f[M], tong[M * 2], p[M];
bool vis[N];
map<int, int> res;
int ans, n, m, r;
struct node{
	int v, w, next;
}edge[M * 2], edge2[M * 2];
void init(){
	memset(head, -1, sizeof(head));
	memset(head2, -1, sizeof(head2));
	memset(vis, false, sizeof(vis));
	memset(f, 0, sizeof(f));
//	memset(res, 0, sizeof(res));
	memset(tong, 0, sizeof(tong));
	cnt = cnt2 = 0;
}

void add(int u, int v){
    edge[cnt].v = v;
	edge[cnt].next = head[u];
	head[u] = cnt++;
}
void add2(int u, int v, int w){
	edge2[cnt2].v = v;
    edge2[cnt2].next = head2[u];
    edge2[cnt2].w = w;
    head2[u] = cnt2++;	
}

int find(int x){
	return x == f[x] ? x : f[x] = find(f[x]);
}

void tarjan(int u){
	vis[u] = true;
	f[u] = u;
	for(int i = head[u]; ~i; i = edge[i].next){
		int v = edge[i].v;
		if(!vis[v]){
			tarjan(v);
			f[v] = u;
		}
	}
	for(int i = head2[u]; ~i; i = edge2[i].next){
		int v = edge2[i].v;
		if(vis[v]){
			res[edge2[i].w] = find(v);
		}
	}
}
signed main(){
	cin >> n >> r >> m;
	init(); 
	for(int i = 1; i < n; i++){
		int u, v;
		cin >> u >> v;
		add(u, v);
		add(v, u);
	}
	int sum = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			//if(i == j) continue;
			add2(i, j, ++sum);
			add2(j, i, sum);
		}
	}
	//cout << sum;
	tarjan(r);
	for(int i = 1; i <= m; i++){
		cin >> p[i];
	}
	int ans = 0;
	for(int i = 1; i <= m; i++){
		for(int j = 1; j <= sum; j++){
		//	cout << res[j] << " "; 
			if(res[j] == p[i]) ans++;
		}
		//cout << endl;
		cout << ans << endl;
		ans = 0;
	}
	return 0;
}
2024/8/17 17:29
加载中...