Submission #604353

#	Time	Username	Problem	Language	Result	Execution time	Memory
604353		amunduzbaev	Mergers (JOI19_mergers)	C++17	100 / 100	969 ms	139584 KiB

mergers

#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef int64_t ll;
#define her cout<<"here"<<endl;

const int N = 5e5 + 5;

struct BIT{
	int tree[N];
	void add(int i, int v){
		for(;i<N;i+=(i&-i)) tree[i] += v;
	}
	
	int get(int i){
		int r = 0;
		for(;i>0;i-=(i&-i)) r += tree[i];
		return r;
	}
}bit;

vector<int> edges[N], G[N];
int a[N], tin[N], tout[N], t;
int par[N][20], pref[N];

void dfs(int u, int p = -1){
	tin[u] = ++t;
	for(int j=1;j<20;j++){
		par[u][j] = par[par[u][j-1]][j-1];
	}
	for(auto x : edges[u]){
		if(x == p) continue;
		par[x][0] = u;
		dfs(x, u);
	}
	
	tout[u] = t;
}

int p[N], sz[N];
int f(int x) { return (p[x] == x ? x : p[x] = f(p[x])); }
void merge(int a, int b){
	a = f(a), b = f(b);
	if(a == b) return;
	if(sz[a] < sz[b]) swap(a, b);
	p[b] = a, sz[a] += sz[b];
}

void dfs2(int u, int p = -1){
	for(auto x : edges[u]){
		if(x == p) continue;
		dfs2(x, u);
		pref[u] += pref[x];
	}
	
	if(pref[u] && ~p){
		merge(u, p);
	}
}

bool is(int a, int b){ return (tin[a] <= tin[b] && tin[b] <= tout[a]); }

int lca(int a, int b){
	if(is(a, b)) return a;
	if(is(b, a)) return b;
	for(int i=19;~i;i--){
		if(!is(par[a][i], b)) a = par[a][i];
	} return par[a][0];
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, k; cin >> n >> k;
	for(int i=1;i<n;i++){
		int a, b; cin >> a >> b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	
	for(int i=1;i<=n;i++){
		cin >> a[i];
		G[a[i]].push_back(i);
	}
	
	par[1][0] = 1;
	dfs(1);
	
	for(int i=1;i<=k;i++){
		vector<int>& t = G[i];
		sort(t.begin(), t.end(), [&](int i, int j){
			return tin[i] < tin[j];
		});
		
		int r = lca(t[0], t.back());
		for(auto u : t){
			pref[r]--;
			pref[u]++;
		}
		
		G[i].clear();
	}
	for(int i=1;i<=n;i++) p[i] = i, sz[i] = 1;
	dfs2(1);
	for(int i=1;i<=n;i++){
		for(auto x : edges[i]){
			if(f(i) != f(x)){
				G[f(i)].push_back(f(x));
			}
		}
	}
	
	int tot = 0;
	for(int i=1;i<=n;i++){
		tot += ((int)G[i].size() == 1);
	}
	
	cout<<(tot + 1) / 2<<"\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30