Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define NMAX 100005
- #define pb push_back
- using namespace std;
- int v[NMAX], fr[NMAX*10],res[2*NMAX],n,sqrt_;
- int LCA[18][NMAX], depth[NMAX];
- bool viz[NMAX];
- int euler[2*NMAX], nrord;
- int in[NMAX], out[NMAX];
- vector<int> G[NMAX];
- struct query {
- int st, dr, i;
- } q[2*NMAX];
- void DFS(int node, int level) {
- euler[++nrord] = node;
- LCA[0][nrord] = node;
- in[node] = nrord;
- depth[node] = level;
- viz[node] = 1;
- for(auto it:G[node])
- if(!viz[it])
- DFS(it, level+1);
- euler[++nrord] = node;
- out[node] = nrord;
- }
- bool mo(query A, query B) {
- if(A.st/sqrt_ == B.st/sqrt_)
- return A.dr < B.dr;
- return A.st/sqrt_ < B.st/sqrt_;
- }
- void remove(int pos, int &ans) {
- --fr[v[pos]];
- if(fr[v[pos]] == 0) --ans;
- }
- void insert(int pos, int &ans) {
- ++fr[v[pos]];
- if(fr[v[pos]] == 1) ++ans;
- }
- int getLCA(int x, int y) {
- if(depth[x] > depth[y]) swap(x,y);
- }
- int main() {
- int m,i,x,y;
- freopen("fisier.in", "r", stdin);
- cin>>n>>m;
- map<int,int> normalized;
- for(i=1;i<=n;++i) {
- cin >> v[i];
- if(normalized.find(v[i]) == normalized.end())
- normalized[v[i]] = normalized.size();
- v[i] = normalized[v[i]];
- }
- for(i=1;i<n;++i) {
- cin>>x>>y;
- G[x].pb(y);
- G[y].pb(x);
- }
- DFS(1,0);
- for(i=1;i<=n;++i) {
- cout << in[i] << ' ' << out[i] << '\n';
- }
- // LCA
- for(i=1;(1<<i)<=nrord;++i) {
- for(j=1;j+(1<<i)-1<=nrord;++j) {
- if(depth[LCA[i-1][j]] < depth[LCA[i-1][j+(1<<i)]])
- LCA[i][j] = LCA[i-1][j];
- else LCA[i][j] = LCA[i-1][j+(1<<i)];
- }
- }
- // for(i=1;i<=m;++i) {
- // cin >> q[i].st >> s[i].dr;
- // q[i].i = i;
- //
- // getLCA(q[i].st, q[i].dr);
- // }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement