제출 #138073

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
138073		MohamedAhmed04	Mergers (JOI19_mergers)	C++14	0 / 100	125 ms	51176 KiB

mergers

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 5e5 + 5 ;

vector< vector<int> >adj(MAX) ;
vector< vector<int> >st(MAX) ;
vector< vector<int> >level(MAX) ;
int n , k;

int state[MAX] , P[MAX][22] , depth[MAX] , lca[MAX];
int lowestdepth[MAX] , nodenum[MAX] , deg[MAX];
int nodes = 0 ;

void dfs(int node , int lvl , int par)
{
	depth[node] = lvl ;
	P[node][0] = par ;
	for(auto &child : adj[node])
	{
		if(child == par)
			continue ;
		dfs(child , lvl + 1 , node) ;
	}
	return ;
}

void preprocess()
{
	dfs(1 , 0 , 0) ;
	for(int j = 1 ; j < 22 ; ++j)
	{
		for(int i = 1 ; i <= n ; ++i)
			P[i][j] = P[P[i][j-1]][j-1] ;
	}
	return ;
}

int LCA(int x , int y)
{
	if(depth[x] < depth[y])
		swap(x , y) ;
	for(int i = 21 ; i >= 0 ; --i)
	{
		if(depth[x] - (1 << i) >= depth[y])
			x = P[x][i] ;
	}
	if(x == y)
		return x ;
	for(int i = 21 ; i >= 0 ; --i)
	{
		if(P[x][i] != P[y][i])
			x = P[x][i] , y = P[y][i] ;
	}
	return P[x][0] ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>k ;
	for(int i = 0 ; i < n-1 ; ++i)
	{
		int x , y ;
		cin>>x>>y ;
		adj[x].push_back(y) ;
		adj[y].push_back(x) ;
	}
	for(int i = 1 ; i <= n ; ++i)
	{
		cin>>state[i] ;
		st[state[i]].push_back(i) ;
	}
	preprocess() ;
	for(int i = 1 ; i <= k ; ++i)
	{
		int lca2 = st[i][0] ;
		for(auto &node : st[i])
			lca2 = LCA(lca2 , node) ;
		if(state[lca2] == i)
			lca2 = P[lca2][0] ;
		for(auto &node : st[i])
		{
			lca[node] = lca2 ;
		}
	}
	int maxdepth = 0 ;
	for(int i = 1 ; i <= n ; ++i)
	{
		level[depth[i]].push_back(i) ;
		maxdepth = max(maxdepth , depth[i]) ;
		lowestdepth[i] = 1e9 ;
	}
	depth[0] = -1 ;
	for(int i = maxdepth ; i >= 0 ; --i)
	{
		for(auto &node : level[i])
		{
			if(nodenum[node] == 0)
			{
				nodes++ ;
				nodenum[node] = nodes ;
			}
			lowestdepth[node] = min(lowestdepth[node] , depth[lca[node]]) ;
			if(i == 0)
				continue;
			if(i-1 == lowestdepth[node])
			{
				if(nodenum[P[node][0]] == 0)
				{
					nodes++ ;
					nodenum[P[node][0]] = nodes ;
				}
				deg[nodenum[P[node][0]]]++ ;
				deg[nodenum[node]]++ ;
			}
			else
			{
				lowestdepth[P[node][0]] = lowestdepth[node] ;
				nodenum[P[node][0]] = nodenum[node] ;
			}
		}
	}
	int cnt = 0 ;
	for(int i = 1 ; i <= n ; ++i)
	{
		if(deg[i] == 1)
			cnt++ ;
	}
	if(cnt == 1)
		cnt = 0 ;
	return cout<<(cnt+1)/2<<"\n" , 0 ;
}

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