#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;
struct Tree{
vector<vector<int> >& adj;
vector<vector<int> > anc;
vector<vector<int> > cost;
vector<int> depth;
vector<int> sub;
vector<bool> vis;
int n;
int root;
Tree(vector<vector<int> >& a, int N = 1e6, int r = 1): adj(a){
n = N + 5;
root = r;
anc = vector<vector<int> > (25, vector<int>(n, 0));
depth = vector<int>(n, 0);
vis = vector<bool> (n, false);
sub = vector<int> (n, 1);
init(root, -1);
for(int d = 1; d < 25; d++){
for(int x = 0; x < n; x++){
anc[d][x] = anc[d - 1][anc[d - 1][x]];
}
}
}
void init(int x, int pre){
for(int i = 0; i < adj[x].size(); i++){
int y = adj[x][i];
if(y == pre)continue;
anc[0][y] = x;
depth[y] = depth[x] + 1;
init(y, x);
sub[x] += sub[y];
}
}
int LCA(int x, int y){
if(depth[x] < depth[y])swap(x,y);
while(depth[x] != depth[y]){
int diff = depth[x] - depth[y];
diff = log2(diff&-diff);
x = anc[diff][x];
}
if(x == y) return x;
for(int i = 24; i >= 0; i--){
if(anc[i][x] != anc[i][y]){
x = anc[i][x];
y = anc[i][y];
}
}
return anc[0][x];
}
int up(int x, int k){
while(k){
int diff = log2(k&-k);
k -= k & -k;
x = anc[diff][x];
}
return x;
}
int dist(int x, int y){
int l = LCA(x, y);
return depth[x] + depth[y] - 2 * depth[l];
}
};
struct DSU{
vector<int> no;
vector<int> size;
int n;
DSU(int n = 2e5 + 5){
no = vector<int> (n);
size = vector<int> (n, 1);
for(int i = 0; i < n; i++) no[i] = i;
}
int Find(int x){
if(no[x] == x) return x;
return no[x] = Find(no[x]);
}
bool merge(int x, int y){
x = Find(x);
y = Find(y);
if(x == y) return false;
if(x > y)swap(x, y);
no[y] = x;
size[x] += size[y];
return true;
}
} dsu(5e5 + 5);
vector<vector<int> > adj(500005);
vector<int> val(500005);
vector<int> comp[500005];
vector<int> up(500005);
vector<int> sub(500005);
void dfs(int x, int pre, vector<int>& depth){
int curr = INF;
for(auto y : adj[x]){
if(y == pre) continue;
dfs(y, x, depth);
if(depth[up[x]] > depth[up[y]])
up[x] = up[y];
}
if(pre != 0 && up[x] != x){
dsu.merge(x, pre);
}
}
int get(int x, int pre){
if(dsu.size[dsu.Find(x)] == 1) sub[x] = 1;
else sub[x] = 0;
for(auto y : adj[x]){
if(y == pre)continue;
get(y, x);
sub[x] += sub[y];
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
cin >> n >> k;
for(int i = 0; i < n - 1; i++) {
int x, y;
cin >> x >> y;
adj[x].pb(y);
adj[y].pb(x);
}
for(int i = 1; i <= n; i++){
cin >> val[i];
comp[val[i]].pb(i);
}
Tree A(adj);
for(int i = 0; i < 500005; i++){
if(comp[i].empty()) continue;
int l = comp[i][0];
for(auto x : comp[i]){
l = A.LCA(x, l);
}
for(auto x : comp[i]){
up[x] = l;
}
}
dfs(1, 0, A.depth);
int root = 1;
for(int i = 1; i <= n; i++) {
if(adj[i].size() == 1) root = i;
}
get(root, 0);
int ans = 0;
if(dsu.size[dsu.Find(root)] == 1) ans++;
for(int x = 1; x <= n; x++){
if(x == root)continue;
if(sub[x] == 1 && dsu.size[dsu.Find(x)] == 1) ans++;
}
cout << (ans + 1) / 2;
}
Compilation message
mergers.cpp: In member function 'void Tree::init(long long int, long long int)':
mergers.cpp:45:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[x].size(); i++){
~~^~~~~~~~~~~~~~~
mergers.cpp: In function 'void dfs(long long int, long long int, std::vector<long long int>&)':
mergers.cpp:163:11: warning: unused variable 'curr' [-Wunused-variable]
int curr = INF;
^~~~
mergers.cpp: In function 'long long int get(long long int, long long int)':
mergers.cpp:183:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
267 ms |
254948 KB |
Output is correct |
| 2 |
Incorrect |
244 ms |
255076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
267 ms |
254948 KB |
Output is correct |
| 2 |
Incorrect |
244 ms |
255076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
267 ms |
254948 KB |
Output is correct |
| 2 |
Incorrect |
244 ms |
255076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
307 ms |
261336 KB |
Output is correct |
| 2 |
Correct |
331 ms |
262144 KB |
Output is correct |
| 3 |
Incorrect |
251 ms |
255080 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
267 ms |
254948 KB |
Output is correct |
| 2 |
Incorrect |
244 ms |
255076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
