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[v] < sz[heavy])){
  44.             v = heavy;
  45.         }
  46.     }
  47.     if (heavy != -1){
  48.         hld(heavy);
  49.     }
  50.     for (int v : g[u]){
  51.         if (v != p[u] && v != heavy){
  52.             numChain++;
  53.             hld(v);
  54.         }
  55.     }
  56. }
  57.  
  58. int lca(int u , int v){
  59.     while (chain[u] != chain[v]){
  60.         if (h[head[chain[u]]] > h[head[chain[v]]]) swap(u , v);
  61.         v = p[head[chain[v]]];
  62.     }
  63.     if (h[u] > h[v]) swap(u , v);
  64.     return u;
  65. }
  66.  
  67. struct fenwich{
  68.     int t[maxN];
  69.  
  70.     void reset(){
  71.         for (int i = 1 ; i <= n ; i++) t[i] = 0;
  72.     }
  73.  
  74.     void update(int x , int y){
  75.         for (; x <= n ; x += x&-x) t[x] += y;
  76.     }
  77.  
  78.     void update(int l , int r , int x){
  79.         update(l , +x);
  80.         update(r + 1 , -x);
  81.     }
  82.  
  83.     int get(int x){
  84.         int ans = 0;
  85.         for (; x >= 1 ; x -= x&-x) ans += t[x];
  86.         return ans;
  87.     }
  88. } fen;
  89.  
  90. void init(){
  91.     for (int i = 1 ; i <= n ; i++){
  92.         fa[i] = -1;
  93.         nxt[i] = i;
  94.     }
  95. }
  96.  
  97. int root(int x){
  98.     if (fa[x] < 0) return x; else return fa[x] = root(fa[x]);
  99. }
  100.  
  101. void unite(int u , int v){
  102.     u = root(u);
  103.     v = root(v);
  104.     if (u == v) return;
  105.     if (-fa[u] < -fa[v]) swap(u , v);
  106.     fa[u] += fa[v];
  107.     fa[v] = u;
  108.     if (h[nxt[u]] > h[nxt[v]]) nxt[u] = nxt[v];
  109. }
  110.  
  111. vector<int> topo;
  112. bool vis[maxN] , cycle = false;
  113.  
  114. void dfs(int id){
  115.     vis[id] = 1;
  116.     int u = nxt[root(s[id])] , v = nxt[root(t[id])];
  117.     while (u != v){
  118.         if (h[u] < h[v]) swap(u , v);
  119.         if (id_query[u] != 0 && id_query[u] != id){
  120.             if (vis[id_query[u]] == 0){
  121.                 dfs(id_query[u]);
  122.             }
  123.         }
  124.         unite(u , p[u]);
  125.         u = nxt[root(u)];
  126.     }
  127.     if (id_query[u] != 0 && id_query[u] != id){
  128.         if (vis[id_query[u]] == 0) dfs(id_query[u]);
  129.     }
  130.     topo.push_back(id);
  131. }
  132.  
  133. void print(){
  134.     fen.reset();
  135.     reverse(all(topo));
  136.     for (int x : topo){
  137.         int u = s[x];
  138.         int v = t[x];
  139.         int vcl = lca(u , v);
  140.         int num = (fen.get(in[u]) + fen.get(in[v])) - (fen.get(in[vcl]) + fen.get(in[p[vcl]]));
  141.         if (num > 0){
  142.             cout << "-1\n";
  143.             return;
  144.         }
  145.         fen.update(in[u] , out[u] , +1);
  146.     }
  147.     reverse(all(topo));
  148.     for (int x : topo) cout << x << " ";
  149. }
  150.  
  151. int id[maxN];
  152.  
  153. void solve(){
  154.     cin >> n >> m;
  155.     for (int i = 1 ; i < n ; i++){
  156.         int u , v;
  157.         cin >> u >> v;
  158.         g[u].push_back(v);
  159.         g[v].push_back(u);
  160.     }
  161.     dfs_init(1);
  162.     for (int i = 1 ; i <= m ; i++){
  163.         cin >> s[i] >> t[i];
  164.         id_query[s[i]] = i;
  165.         id[i] = i;
  166.     }
  167.     init();
  168.     sort(id + 1 , id + m + 1 , [](int x , int y){
  169.          return h[s[x]] > h[s[y]];
  170.     });
  171.     for (int i = 1 ; i <= m ; i++){
  172.         if (vis[id[i]] == 0) dfs(id[i]);
  173.     }
  174.     print();
  175. }
  176.  
  177. #define name "E"
  178.  
  179. int main(){
  180.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  181.     if (fopen(name".INP" , "r")){
  182.         freopen(name".INP" , "r" , stdin);
  183.         freopen(name".OUT" , "w" , stdout);
  184.     }
  185.     int t = 1; //cin >> t;
  186.     while (t--) solve();
  187.     return 0;
  188. }
  189.  
  190.  
Success #stdin #stdout 0.01s 24148KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/EzJQFI
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!