Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- #define debug(x) cerr << '[' << (#x) << "] = " << x << '\n';
- template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update> ;
- const int block_size = 800;
- // 0 based indexing
- class MosAlgorithm {
- public:
- struct Query {
- int l, r, index;
- bool operator< (Query o) const {
- return make_pair(make_pair(l/block_size, r), index) < make_pair(make_pair(o.l/block_size, o.r), o.index);
- };
- };
- int N, M; // N -> Query count, M -> Max element
- vector<Query>queries;
- vector<int>range, A;
- MosAlgorithm(vector<pair<int,int>>&_queries) {
- N = _queries.size();
- for(int i=0; i<N; ++i) {
- Query q = {_queries[i].first, _queries[i].second, i};
- queries.push_back(q);
- }
- sort(queries.begin(), queries.end());
- }
- void Hash(vector<int>a) {
- map<int,int>H;
- A = a;
- for(int i=0; i<A.size(); ++i) H[A[i]] = 0;
- int cur = 0;
- for(auto &it : H) it.second = cur++;
- for(int i=0; i<A.size(); ++i) A[i] = H[A[i]];
- M = cur;
- range.resize(M+1, 0);
- }
- vector<int>process() {
- int L = 0, R = -1, cur = 0;
- vector<int>ret(N);
- for(Query q : queries) {
- while(L > q.l) {
- if(++range[A[--L]]==1) ++cur;
- }
- while(R < q.r) {
- if(++range[A[++R]]==1) ++cur;
- }
- while(L < q.l) {
- if(--range[A[L++]]==0) --cur;
- }
- while(R > q.r) {
- if(--range[A[R--]]==0) --cur;
- }
- ret[q.index] = cur;
- }
- return ret;
- }
- };
- void PlayGround() {
- int n; cin >> n;
- vector<int>a(n), b(n);
- vector<vector<int>>edges(n, vector<int>());
- for(auto& it : a) cin >> it;
- for(int i=1; i<n; ++i) {
- int u, v; cin >> u >> v;
- --u, --v;
- edges[u].push_back(v);
- edges[v].push_back(u);
- }
- vector<pair<int,int>>p(n);
- int timer = 0;
- function<void(int,int)> DFS = [&] (int node, int parent) {
- p[node].first = timer;
- b[timer++] = a[node];
- for(auto it : edges[node]) if(it!=parent) {
- DFS(it, node);
- }
- p[node].second = timer-1;
- };
- DFS(0,0);
- MosAlgorithm Mo(p);
- Mo.Hash(b);
- for(int ans : Mo.process()) {
- cout << ans << ' ';
- }
- cout << '\n';
- #ifndef ONLINE_JUDGE
- cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
- #endif
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- #endif
- PlayGround();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
