Submission #1299816

#TimeUsernameProblemLanguageResultExecution timeMemory
1299816onur8ocakRailway (BOI17_railway)C++20
0 / 100
73 ms35612 KiB
#include <bits/stdc++.h>

using namespace std;
#define int long long
#define pb push_back
#define all(v) v.begin(), v.end()
#define F first
#define S second

const int N = 100000;

int lift[N][21];
vector<int> adj[N],level(N,0),dep(N,0),v(N,0),ans;
map<pair<int,int>, int> E;
int cnt = 0,n,m,k;

void dfs(int node,int p){
	level[node] = cnt++;
	dep[node] = (node != 0) ? dep[p] + 1 : 1;
	lift[node][0] = p;
	for(auto go : adj[node]){
		if(go != p) dfs(go, node);
	}
}

int dfsans(int node,int p){
	int sm = v[node];
	for(auto go : adj[node]){ 
	    if(go != p) sm += dfsans(go, node);
	}
	if(sm / 2 >= k) ans.pb(E[{min(node, p), max(node, p)}]);
	return sm;
}

int LCA(int x,int y){
	for(int layer = 19; layer >= 0; layer--){
		if(dep[x] - dep[y] >= (1ll << layer)) x = lift[x][layer];
		
		if(dep[y] - dep[x] >= (1ll << layer)) y = lift[y][layer];
	}
	
	if(x == y) return x;
	
	for(int layer = 19; layer >= 0; layer--){
		if(lift[x][layer] != lift[y][layer]){
			x = lift[x][layer];
			y = lift[y][layer];
		}
	}
	
	return lift[x][0];
}

void calclift(){
	for(int layer = 1; layer <= 19; layer++){
		for(int i = 0; i < n; i++) lift[i][layer] = lift[lift[i][layer-1]][layer-1];
	}
}

void _(){
	cin >> n >> m >> k;
	
	for(int i = 1; i <= n - 1; i++){
		int u,v;
		cin >> u >> v;
		u--,v--;
		adj[u].pb(v);
		adj[v].pb(u);
		E[{min(u, v), max(u, v)}] = i;
	}
	
	dfs(0, -1);
	calclift();
	
	while(m--){
		int siz;
		cin >> siz;
		deque<int> nodes;
		
		for(int i = 0; i < siz; i++){
			int x;
			cin >> x;
			x--;
			nodes.pb(x);
		}
		
		sort(all(nodes), [](int a, int b){
			return level[a] < level[b];
		});
		
		int lowest = nodes[0];
		for(int i = 1; i < siz; i++) lowest = LCA(lowest, nodes[i]);
		nodes.push_front(lowest);
		
		for(int i = 0; i < nodes.size(); i++){
			int anc = LCA(nodes[i], nodes[(i + 1) % nodes.size()]);
			v[anc] -= 2;
			v[nodes[i]] += 1;
			v[nodes[(i + 1) % nodes.size()]] += 1;
		}
		
	}
	
	dfsans(0, -1);
	
	cout << ans.size() << endl;
	for(auto pr : ans) cout << pr << " ";
	cout << endl;
}

int32_t main()
{
    int t = 1;
    //cin >> t;
    while(t--) _();

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...