Submission #411022

#	Time	Username	Problem	Language	Result	Execution time	Memory
411022		alireza_kaviani	Mergers (JOI19_mergers)	C++11	0 / 100	108 ms	42180 KiB

mergers

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

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)						(x).begin(),(x).end()
#define X							first
#define Y							second
#define sep							' '
#define endl						'\n'
#define SZ(x)						ll(x.size())

const ll MAXN = 5e5 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

int n , k , timer , ans , col[MAXN] , par[LOG][MAXN] , H[MAXN] , st[MAXN] , ps[MAXN] ,mark[MAXN];
vector<int> adj[MAXN] , vec[MAXN];

int cmp(int x , int y){
	return st[x] < st[y];
}

void PreDFS(int v , int p = 0){
	par[0][v] = p;
	st[v] = timer++;
	H[v] = H[p] + 1;
	for(int u : adj[v]){
		if(u == p)	continue;
		PreDFS(u , v);
	}
}

int getPar(int v , int h){
	for(int i = 0 ; i < LOG ; i++){
		if(h & (1 << i)){
			v = par[i][v];
		}
	}
	return v;
}

int LCA(int v , int u){
	if(H[v] > H[u])	swap(v , u);
	u = getPar(u , H[u] - H[v]);
	if(v == u)	return v;
	for(int i = LOG - 1 ; i >= 0 ; i--){
		if(par[i][v] != par[i][u]){
			v = par[i][v];
			u = par[i][u];
		}
	}
	return par[0][v];
}

void SolveDFS(int v , int p = -1){
	for(int u : adj[v]){
		if(u == p)	continue;
		SolveDFS(u , v);
		ps[v] += ps[u];
		if(ps[u] == 0 && mark[u] == 0)	ans++;
		if(ps[u] == 0)	mark[v] = 1;
		mark[v] |= mark[u];
	}
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin >> n >> k;
	for(int i = 1 ; i < n ; i++){
		int v , u;
		cin >> v >> u;
		adj[v].push_back(u);
		adj[u].push_back(v);
	}
	for(int i = 1 ; i <= n ; i++){
		cin >> col[i];
		vec[col[i]].push_back(i);
	}
	PreDFS(1);
	for(int i = 1 ; i < LOG ; i++){
		for(int j = 0 ; j <= n ; j++){
			par[i][j] = par[i - 1][par[i - 1][j]];
		}
	}
	for(int i = 1 ; i <= k ; i++){
		sort(all(vec[i]) , cmp);
		for(int j = 0 ; j + 1 < SZ(vec[i]) ; j++){
			int v = vec[i][j] , u = vec[i][j + 1];
			int lca = LCA(v , u);
			ps[v]++; ps[u]++; ps[lca] -= 2;
		}
	}
	SolveDFS(1);
	cout << (ans + 1) / 2 << endl;

    return 0;
}
/*

*/

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