fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. bool memory1;
  4.  
  5. typedef long long ll;
  6. typedef unsigned long long ull;
  7. typedef double dbe;
  8. typedef pair<ll, ll> pll;
  9. typedef vector<ll> vll;
  10. typedef vector<int> vii;
  11.  
  12. #define openFile(name) freopen((name ".inp"), "r", stdin), freopen((name ".out"), "w", stdout)
  13. #define FOR(i, a, b, x) for (int i = (a); i <= (b); i += (x))
  14. #define ROF(i, a, b, x) for (int i = (a); i >= (b); i += (x))
  15. #define fi first
  16. #define se second
  17. #define MASK(x) (1LL << (x))
  18. #define getBit(mask, i) (((mask) >> (i)) & 1)
  19. #define BitOn(mask) (__builtin_popcountll(mask))
  20.  
  21. const int maxN = 5e4 + 2;
  22. //const ll maxBit = MASK(8) + 2;
  23. const ll LOG = 16;
  24. const ll INF18 = 1e18;
  25. const int INF9 = 1e9;
  26. //const ll INF3f = 0x3f3f3f3f3f3f3f3f;
  27. const ll MOD = 1e9 + 7;
  28. //////////////////////////////////////////////
  29. const ll BL = 256;
  30.  
  31. struct Query12 {
  32.     int ty, id;
  33.     Query12(int t = 0, int i = 0) : ty(t), id(i) {}
  34. };
  35.  
  36. struct Query3 {
  37.     int u, v, id;
  38.     Query3(int uu = 0, int vv = 0, int i = 0) : u(uu), v(vv), id(i) {}
  39. };
  40.  
  41. int n, m, timeDFS;
  42. int a[maxN];
  43. int ans[maxN];
  44.  
  45. int sz[maxN];
  46. int h[maxN];
  47. int tin[maxN], tout[maxN];
  48. int d[maxN][maxN / BL + 5]; // goc u
  49. int f[maxN][maxN / BL + 5]; // 1 -> u
  50. int pa[maxN][LOG + 2];
  51. int ver[maxN];
  52.  
  53. int mark[maxN];
  54. int colID[maxN];
  55.  
  56. map<int, int> mp;
  57. vii stColor;
  58. vii adj[maxN];
  59. vector<Query12> qr12[maxN];
  60. vector<Query3> qr3;
  61. vii colBL;
  62.  
  63. void dfs(int u) {
  64.     tin[u] = ++timeDFS;
  65.     ++d[u][colID[a[u]]];
  66.     ++sz[u];
  67.     ver[tin[u]] = u;
  68.     ++f[u][colID[a[u]]];
  69.  
  70.     for (int v : adj[u]) if (v != pa[u][0]) {
  71.         pa[v][0] = u;
  72.         h[v] = h[u] + 1;
  73.  
  74.         FOR (i, 1, LOG, 1) pa[v][i] = pa[pa[v][i - 1]][i - 1];
  75.  
  76.         for (ll col : colBL) f[v][colID[col]] += f[u][colID[col]];
  77.  
  78.         dfs(v);
  79.  
  80.         for (ll col : colBL)
  81.             d[u][colID[col]] += d[v][colID[col]];
  82.  
  83.         sz[u] += sz[v];
  84.     }
  85.     tout[u] = timeDFS;
  86. }
  87.  
  88. void add(ll u) {
  89.     ++mp[a[u]];
  90. }
  91.  
  92. void sack(ll u, bool keep) {
  93.     int bigC = -1;
  94.     for (int v : adj[u]) if (v != pa[u][0])
  95.         if (bigC == -1 || sz[bigC] < sz[v])
  96.             bigC = v;
  97.  
  98.     for (int v : adj[u]) if (v != pa[u][0] && v != bigC)
  99.         sack(v, false);
  100.  
  101.     if (bigC != -1)
  102.         sack(bigC, true);
  103.  
  104.     add(u);
  105.     for (int v : adj[u])
  106.         if (v != pa[u][0] && v != bigC)
  107.             FOR (i, tin[v], tout[v], 1)
  108.                 add(ver[i]);
  109.  
  110.     int siz;
  111.     for (Query12 &q : qr12[u]) {
  112.         int col = -1;
  113.         if (q.ty == 1) {
  114.             siz = sz[u];
  115.             if (siz < 2 * BL) {
  116.                 for (pair<int, int> p : mp) // col cnt
  117.                     if (p.se > siz / 2) {
  118.                         col = p.fi;
  119.                         break;
  120.                     }
  121.             }
  122.             else
  123.                 for (int c : colBL)
  124.                     if (d[u][colID[c]] > siz / 2) {
  125.                         col = c;
  126.                         break;
  127.                     }
  128.         }
  129.         else {
  130.             siz = n - sz[u];
  131.             if (siz < 2 * BL) {
  132.                 for (int c : stColor) // col cnt
  133.                     if (mark[c] - mp[c] > siz / 2) {
  134.                         col = c;
  135.                         break;
  136.                     }
  137.             }
  138.             if (col == -1)
  139.                 for (int c : colBL)
  140.                     if (d[1][colID[c]] - d[u][colID[c]] > siz / 2) {
  141.                         col = c;
  142.                         break;
  143.                     }
  144.         }
  145.         ans[q.id] = col;
  146.     }
  147.     if (!keep) mp.clear();
  148. }
  149.  
  150. int lca(int u, int v) {
  151.     if (h[u] != h[v]) {
  152.         if (h[u] < h[v]) swap(u, v);
  153.         int k = h[u] - h[v];
  154.         for (int i = 0; MASK(i) <= k; ++i)
  155.             if (getBit(k, i))
  156.                 u = pa[u][i];
  157.     }
  158.     if (u == v) return u;
  159.  
  160.     int k = __lg(h[u]);
  161.     ROF (i, k, 0, -1)
  162.         if (pa[u][i] != pa[v][i]) {
  163.             u = pa[u][i];
  164.             v = pa[v][i];
  165.         }
  166.     return pa[u][0];
  167. }
  168.  
  169. int pathCol(int u, int v, int p, int sz) {
  170.     map<int, int> cnt;
  171.     while (u != p) {
  172.         ++cnt[a[u]];
  173.         u = pa[u][0];
  174.     }
  175.     while (v != p) {
  176.         ++cnt[a[v]];
  177.         v = pa[v][0];
  178.     }
  179.     ++cnt[a[p]];
  180.     for (pair<int, int> p : cnt) // col cnt
  181.         if (p.se > sz / 2)
  182.             return p.fi;
  183.     return -1;
  184. }
  185.  
  186. void Solve() {
  187.     sort(colBL.begin(), colBL.end());
  188.  
  189.     for (int col : colBL)
  190.         colID[col] = lower_bound(colBL.begin(), colBL.end(), col) - colBL.begin() + 1;
  191.  
  192.     FOR (i, 1, n, 1) if (0 < mark[i] && mark[i] < BL) stColor.push_back(i);
  193.  
  194.     h[1] = 1;
  195.     dfs(1);
  196.     sack(1, false);
  197.     // truy van 3
  198.     for (Query3 &q : qr3) {
  199.         int u = q.u, v = q.v;
  200.         int p = lca(u, v);
  201.         int sz = h[u] + h[v] - 2 * h[p] + 1;
  202.         ans[q.id] = -1;
  203.  
  204.         if (sz <= BL * 2)
  205.             ans[q.id] = pathCol(u, v, p, sz);
  206.         else {
  207.             for (int col : colBL) {
  208.                 int cID = colID[col];
  209.                 int val = f[u][cID] + f[v][cID] - 2 * f[p][cID];
  210.                 if (a[p] == col) ++val;
  211.  
  212.                 if (val > sz / 2) {
  213.                     ans[q.id] = col;
  214.                     break;
  215.                 }
  216.             }
  217.         }
  218.     }
  219.  
  220.     FOR (i, 1, m, 1) cout << ans[i] << "\n";
  221. }
  222.  
  223. void input() {
  224.     cin >> n >> m;
  225.     FOR (i, 1, n, 1) {
  226.         cin >> a[i];
  227.         ++mark[a[i]];
  228.         if (mark[a[i]] == BL) colBL.push_back(a[i]);
  229.     }
  230.     int u, v, ty;
  231.     FOR (i, 2, n, 1) {
  232.         cin >> u >> v;
  233.         adj[u].push_back(v);
  234.         adj[v].push_back(u);
  235.     }
  236.     FOR (i, 1, m, 1) {
  237.         cin >> ty;
  238.         if (ty == 1 || ty == 2) {
  239.             cin >> u;
  240.             qr12[u].emplace_back(ty, i);
  241.         }
  242.         else {
  243.             cin >> u >> v;
  244.             qr3.emplace_back(u, v, i);
  245.         }
  246.     }
  247.     Solve();
  248. }
  249.  
  250.  
  251. int main() {
  252.     openFile("TQUERY");
  253.     ios_base::sync_with_stdio(0);
  254.     cin.tie(0);
  255.     input();
  256.  
  257.     //bool memory2;
  258.     //cerr << "\n\n\nTime: "<< 1000.0 * clock() / CLOCKS_PER_SEC << " ms";
  259.     //cerr << "\n\n\nMemory: "<< abs(&memory1 - &memory2) * 1.0 / MASK(20) <<" MB";
  260.  
  261.     return 0;
  262. }
  263. // nhan0123456
Success #stdin #stdout 0.01s 12676KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/j4Khiv
language:
C++ (gcc 8.3)
created:
7 days 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!