mnzn求助,0pts,样例过不了
查看原帖
mnzn求助,0pts,样例过不了
360265
Galois_Field_1048576楼主2022/1/17 11:44
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
#define ll long long
const int nil = -1;
struct node {int to, id;}; 
vector <node> tree[200100];
int father[20][200100], depth[200100], n, m, k, s, ask[200100], ans;
int time_stamp, diff[200100], dfn[200100], need[200100]; 
void dfs(int ths, int fa) {
	father[0][ths] = fa;
	dfn[ths] = (++time_stamp) ;
	for (int i = 1; i < 18; ++i) 
		father[i][ths] = father[i - 1][father[i - 1][ths]];
	for (node it : tree[ths])
		if (it.to != fa) 
			depth[it.to] = depth[ths] + 1,
			dfs(it.to,ths);
}
bool cmp(int x, int y) {
	return dfn[x] < dfn[y];
} 
int lca(int l, int r) {
	if (depth[l] < depth[r]) swap(l, r);
	for (int i = 17; i >= 0; --i) 
		if (depth[father[i][l]] >= depth[r])
			l = father[i][l];
	if (l == r) return r;
	for (int i = 17; i >= 0; --i)
		if (father[i][l] != father[i][r]) {
			l = father[i][l]; r = father[i][r];
		}
	return father[0][l];
	
}
void solve(int x,int fa) {
	for (node j : tree[x]) 
		if (j.to != fa){
		int i = j.to;
		//cout << x << ' ' << i << ' ' << j.id << ' ' << diff[x] << ' ' << diff[i] << endl;
		solve(i,x);
		//cout << x << ' ' << i << ' ' << j.id << ' ' << diff[x] << ' ' << diff[i] << endl;
		if (diff[i] >= 2*k) ans ++, need[j.id] = true;
		//cout << x << ' ' << i << ' ' << j.id << ' ' << diff[x] << ' ' << diff[i] << endl;
		diff[x] += diff[i]; // 前缀和,抵消差分。 
		//cout << x << ' ' << i << ' ' << j.id << ' ' << diff[x] << ' ' << diff[i] << endl;
	} 
} 
int main() {
	cin >> n >> m >> k;
	father[0][1] = 1;
	depth[1] = 0;
	for (int i = 1; i < n; ++i) {
		int a, b; cin >> a >> b;
		tree[a].push_back({b,i});
		tree[b].push_back({a,i}); 
		
	}
	dfs(1,nil);
	for (int i = 1; i <= m; ++i) {
		cin >> s;
		for (int i = 1; i <= s; ++i) cin >> ask[i];
		sort(ask+1,ask+s+1,cmp);
		for(int j = 1; j < s; j++) { 
			diff[ask[j]]++;
			diff[ask[j+1]]++;
			diff[lca(ask[i], ask[j+1])] -= 2;
		} 
		diff[ask[s]]++;
		diff[ask[1]]++;
		diff[lca(ask[s], ask[1])] -= 2;
	} 
	solve(1,nil);
	cout << ans << endl;
	for (int i = 1 ; i < 200100 ; ++ i)
		if(need[i]) cout << i << ' ';
}
2022/1/17 11:44
加载中...