fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define all(v) v.begin() , v.end()
  5. #define sz(v) int(v.size())
  6. #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef pair<int , int> ii;
  11. typedef pair<long long , int> lli;
  12.  
  13. const int maxN = int(5e5)+7;
  14.  
  15. int n , m;
  16. int id_query[maxN] , s[maxN] , t[maxN];
  17. vector<int> g[maxN];
  18. int fa[maxN] , nxt[maxN];
  19. int h[maxN] , p[maxN] , sz[maxN] , in[maxN] , out[maxN] , DfsTime = 0;
  20.  
  21. void dfs_init(int u){
  22.     in[u] = ++DfsTime;
  23.     sz[u] = 1;
  24.     for (int v : g[u]){
  25.         if (v != p[u]){
  26.             p[v] = u;
  27.             h[v] = h[u] + 1;
  28.             dfs_init(v);
  29.             sz[u] += sz[v];
  30.         }
  31.     }
  32.     out[u] = DfsTime;
  33. }
  34.  
  35. int head[maxN] , chain[maxN] , pos[maxN] , numChain = 0 , numPos = 0;
  36.  
  37. void hld(int u){
  38.     if (head[numChain] == 0) head[numChain] = u;
  39.     chain[u] = numChain;
  40.     pos[u] = ++numPos;
  41.     int heavy = -1;
  42.     for (int v : g[u]){
  43.         if (v != p[u] && (heavy == -1 || sz[heavy] < sz[v])) heavy = v;
  44.     }
  45.     if (heavy != -1) hld(heavy);
  46.     for (int v : g[u]){
  47.         if (v != p[u] && v != heavy){
  48.             numChain++;
  49.             hld(v);
  50.         }
  51.     }
  52. }
  53.  
  54. int lca(int u , int v){
  55.     while (chain[u] != chain[v]){
  56.         if (h[head[chain[u]]] > h[head[chain[v]]]) swap(u , v);
  57.         v = p[head[chain[v]]];
  58.     }
  59.     if (h[u] > h[v]) swap(u , v);
  60.     return u;
  61. }
  62.  
  63. struct fenwich{
  64.     int t[maxN];
  65.  
  66.     void reset(){
  67.         for (int i = 1 ; i <= n ; i++) t[i] = 0;
  68.     }
  69.  
  70.     void update(int x , int y){
  71.         for (; x <= n ; x += x&-x) t[x] += y;
  72.     }
  73.  
  74.     void update(int l , int r , int x){
  75.         update(l , +x);
  76.         update(r + 1 , -x);
  77.     }
  78.  
  79.     int get(int x){
  80.         int ans = 0;
  81.         for (; x >= 1 ; x -= x&-x) ans += t[x];
  82.         return ans;
  83.     }
  84. } fen;
  85.  
  86. void init(){
  87.     for (int i = 1 ; i <= n ; i++){
  88.         fa[i] = -1;
  89.         nxt[i] = i;
  90.     }
  91. }
  92.  
  93. int root(int x){
  94.     if (fa[x] < 0) return x; else return fa[x] = root(fa[x]);
  95. }
  96.  
  97. void unite(int u , int v){
  98.     u = root(u);
  99.     v = root(v);
  100.     if (u == v) return;
  101.     if (-fa[u] < -fa[v]) swap(u , v);
  102.     fa[u] += fa[v];
  103.     fa[v] = u;
  104.     if (h[nxt[u]] > h[nxt[v]]) nxt[u] = nxt[v];
  105. }
  106.  
  107. vector<int> topo;
  108. bool vis[maxN] , cycle = false;
  109.  
  110. void dfs(int id){
  111.     vis[id] = 1;
  112.     int u = nxt[root(s[id])] , v = nxt[root(t[id])];
  113.     while (u != v){
  114.         if (h[u] < h[v]) swap(u , v);
  115.         if (id_query[u] != 0 && id_query[u] != id){
  116.             if (vis[id_query[u]] == 0){
  117.                 dfs(id_query[u]);
  118.             }
  119.         }
  120.         unite(u , p[u]);
  121.         u = nxt[root(u)];
  122.     }
  123.     if (id_query[u] != 0 && id_query[u] != id){
  124.         if (vis[id_query[u]] == 0) dfs(id_query[u]);
  125.     }
  126.     topo.push_back(id);
  127. }
  128.  
  129. void print(){
  130.     fen.reset();
  131.     reverse(all(topo));
  132.     for (int x : topo){
  133.         int u = s[x];
  134.         int v = t[x];
  135.         int vcl = lca(u , v);
  136.         int num = (fen.get(in[u]) + fen.get(in[v])) - (fen.get(in[vcl]) + fen.get(in[p[vcl]]));
  137.         if (num > 0){
  138.             cout << "-1\n";
  139.             return;
  140.         }
  141.         fen.update(in[u] , out[u] , +1);
  142.     }
  143.     reverse(all(topo));
  144.     for (int x : topo) cout << x << " ";
  145. }
  146.  
  147. int id[maxN];
  148.  
  149. void solve(){
  150.     cin >> n >> m;
  151.     for (int i = 1 ; i < n ; i++){
  152.         int u , v;
  153.         cin >> u >> v;
  154.         g[u].push_back(v);
  155.         g[v].push_back(u);
  156.     }
  157.     dfs_init(1);
  158.     hld(1);
  159.     for (int i = 1 ; i <= m ; i++){
  160.         cin >> s[i] >> t[i];
  161.         id_query[s[i]] = i;
  162.         id[i] = i;
  163.     }
  164.     init();
  165.     sort(id + 1 , id + m + 1 , [](int x , int y){
  166.          return h[s[x]] > h[s[y]];
  167.     });
  168.     for (int i = 1 ; i <= m ; i++){
  169.         if (vis[id[i]] == 0) dfs(id[i]);
  170.     }
  171.     print();
  172. }
  173.  
  174. #define name "E"
  175.  
  176. int main(){
  177.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  178.     if (fopen(name".INP" , "r")){
  179.         freopen(name".INP" , "r" , stdin);
  180.         freopen(name".OUT" , "w" , stdout);
  181.     }
  182.     int t = 1; //cin >> t;
  183.     while (t--) solve();
  184.     return 0;
  185. }
  186.  
  187.  
Success #stdin #stdout 0.01s 26220KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/VR78O0
language:
C++ (gcc 8.3)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!