#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
#define MAXN 500005
#define LOGM 22
int par[LOGM][MAXN];
int lev[MAXN];
int mark[MAXN];
int type[MAXN];
int tar[MAXN];
std::vector<int> Adj[MAXN];
std::vector<int> coll[MAXN];
std::pair<int, int> ord[MAXN];
std::queue<int> q;
std::stack<int> s;
int deg[MAXN];
void dfs()
{
while(!s.empty())
{
int u = s.top(); s.pop();
int p;
if(s.empty())
p = 0;
else
p = s.top();
lev[u] = 0;
if(p)
{
par[0][u] = p;
lev[u] = lev[p]+1;
}
for(int i = 1; i < LOGM; i++)
{
if(par[i-1][u] > 0)
par[i][u] = par[i-1][par[i-1][u]];
}
for(int v : Adj[u])
{
if(v == p)
continue;
s.push(v);
}
}
}
int lca(int u, int v)
{
if(lev[u] > lev[v])
u ^= v ^= u ^= v;
for(int i = LOGM-1; i >= 0; i--)
{
if(lev[v]-lev[u] >= (1 << i))
v = par[i][v];
}
if(u == v)
return u;
for(int i = LOGM-1; i >= 0; i--)
{
if(par[i][u] != par[i][v])
{
u = par[i][u];
v = par[i][v];
}
}
return par[0][u];
}
int main()
{
int n, k;
std::cin >> n >> k;
for(int i = 1; i < n; i++)
{
int a, b;
std::cin >> a >> b;
Adj[a].push_back(b);
Adj[b].push_back(a);
}
s.push(1);
dfs();
for(int i = 1; i <= n; i++)
{
int t;
std::cin >> t;
coll[t].push_back(i);
type[i] = t;
if(tar[t] == 0)
tar[t] = i;
else
tar[t] = lca(tar[t], i);
}
for(int i = 0; i < k; i++)
{
ord[i] = {lev[tar[i+1]], i+1};
}
std::sort(ord, ord+k);
for(int i = 0; i < k; i++)
{
int t = ord[i].second;
if(mark[t])
continue;
q.push(t);
mark[t] = i+1;
while(!q.empty())
{
int c = q.front(); q.pop();
for(int j : coll[c])
{
if(j == tar[t])
continue;
int v = type[par[0][j]];
if(!mark[v])
{
mark[v] = i+1;
q.push(v);
}
}
}
}
int ans = 1;
for(int i = 1; i <= n; i++)
{
for(int j : Adj[i])
if(mark[type[i]] != mark[type[j]])
deg[mark[type[i]]]++;
}
for(int i = 1; i <= k; i++)
if(deg[i] == 1)
ans++;
std::cout << ans/2;
std::cout << std::endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
903 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
903 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
903 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
426 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
903 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |