/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 3010;
int n, k, state[maxn];
vector < int > adj[maxn], group[maxn];
void input()
{
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 >> state[i];
group[state[i]].push_back(i);
}
}
int tin[maxn], tout[maxn], timer;
int occ[2 * maxn], depth[maxn], par[maxn];
void dfs(int v, int p)
{
tin[v] = ++ timer;
occ[timer] = v;
par[v] = p;
for (int u : adj[v])
{
if (u == p)
continue;
depth[u] = depth[v] + 1;
dfs(u, v);
occ[++ timer] = v;
}
tout[v] = timer;
}
const int maxlog = 22;
int dp[maxlog][maxn * 2], lg[maxn * 2];
void build_sparse_table()
{
for (int i = 1; i <= timer; i ++)
{
lg[i] = lg[i / 2] + 1;
dp[0][i] = occ[i];
}
for (int j = 1; j < lg[timer]; j ++)
for (int i = 1; i <= timer - (1 << j) + 1; i ++)
{
dp[j][i] = dp[j - 1][i + (1 << (j - 1))];
if (depth[dp[j - 1][i]] < depth[dp[j][i]])
dp[j][i] = dp[j - 1][i];
}
}
int get_lca(int v, int u)
{
v = tin[v];
u = tin[u];
if (v > u)
swap(v, u);
int len = lg[u - v + 1] - 1;
int res = dp[len][u - (1 << len) + 1];
if (depth[dp[len][v]] < depth[res])
res = dp[len][v];
return res;
}
int mark[maxn];
void mark_path(int v, int u)
{
int lca = get_lca(v, u);
while(v != lca)
{
mark[v] = 1;
v = par[v];
}
while(u != lca)
{
mark[u] = 1;
u = par[u];
}
}
void find_redundant()
{
for (int d = 1; d <= k; d ++)
{
for (int i = 1; i < group[d].size(); i ++)
{
mark_path(group[d][i - 1], group[d][i]);
}
}
}
vector < int > g[maxn];
int used[maxn];
int cp_cnt;
void trav(int v)
{
used[v] = cp_cnt;
for (int u : g[v])
{
if (used[u] != 0)
continue;
trav(u);
}
}
vector < int > bridge[maxn];
void build_new_graph()
{
/// exclude 1
for (int i = 2; i <= n; i ++)
{
if (mark[i])
{
g[i].push_back(par[i]);
g[par[i]].push_back(i);
}
}
//for (int i = 1; i <= n; i ++)
// cout << "mark " << i << " " << mark[i] << endl;
for (int i = 1; i <= n; i ++)
{
if (!used[i])
{
cp_cnt ++;
trav(i);
}
}
//for (int i = 1; i <= n; i ++)
// cout << i << " " << used[i] << endl;
for (int i = 2; i <= n; i ++)
{
if (!mark[i])
{
assert(used[par[i]] != used[i]);
bridge[used[i]].push_back(used[par[i]]);
bridge[used[par[i]]].push_back(used[i]);
}
}
}
int find_leaves(int v, int p)
{
int child = 0, leaves = 0;
used[v] = 1;
for (int u : bridge[v])
{
if (used[u] == 1)
continue;
child ++;
leaves += find_leaves(u, v);
}
if ((p == -1 && child < 2) || child == 0)
leaves ++;
return leaves;
}
void print()
{
memset(used, 0, sizeof(used));
int res = find_leaves(1, - 1);
cout << res - 1 << endl;
}
void solve()
{
input();
dfs(1, -1);
build_sparse_table();
find_redundant();
build_new_graph();
print();
}
int main()
{
solve();
return 0;
}
Compilation message
mergers.cpp: In function 'void find_redundant()':
mergers.cpp:117:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for (int i = 1; i < group[d].size(); i ++)
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
1116 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
