This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pb push_back
#define ins isnert
#define pii pair<int,int>
#define ff first
#define ss second
#define loop(i,a,b) for(int i = (a); i < (b); i ++)
#define op(x) cerr << #x << " = " << x << endl;
#define opa(x) cerr << #x << " = " << x << ", ";
#define ops(x) cerr << x;
#define spac cerr << ' ';
#define entr cerr << endl;
#define STL(x) cerr << #x << " : "; for(auto &qwe:x) cerr << qwe << ' '; cerr << endl;
#define ARR(x, nnn) cerr << #x << " : "; loop(qwe,0,nnn) cerr << x[qwe] << ' '; cerr << endl;
#define BAE(x) (x).begin(), (x).end()
#define bye exit(0);
using namespace std;
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int mxn = (int)(1e5) + 10;
vector<int> E[mxn];
int col[mxn];
vector<int> vec_col[mxn];
void dfs(int v, int par, int dis){
vec_col[dis].pb(col[v]);
for(auto &u:E[v]){
if(u == par) continue;
dfs(u, v, dis + 1);
}
}
void test_dfs(int v, int par){
for(auto &u:E[v]){
if(u == par) continue;
test_dfs(u, v);
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
int n, m; cin >> n >> m;
loop(i,0,n-1){
int a, b;
cin >> a >> b;
E[a].pb(b);
E[b].pb(a);
}
vector<int> srt_col;
loop(i,1,n+1){
cin >> col[i];
srt_col.pb(col[i]);
}
sort(BAE(srt_col));
srt_col.resize(unique(BAE(srt_col)) - srt_col.begin());
loop(i,1,n+1){
col[i] = lower_bound(BAE(srt_col), col[i]) - srt_col.begin() + 1;
}
if(n > 2000){
loop(i,1,n+1){
test_dfs(i, -1);
}
return 0;
}
loop(i,1,n+1){
loop(i,1,n+1) vec_col[i].clear();
vector<int> vec_ans;
dfs(i, -1, 0);
loop(i,1,n+1){
if(vec_col[i].size() == 1){
vec_ans.pb(vec_col[i][0]);
}
}
sort(BAE(vec_ans));
vec_ans.resize(unique(BAE(vec_ans)) - vec_ans.begin());
cout << vec_ans.size() << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |