题解：P16395 [ECUSTPC 2026 Spring] 星之所在

· · 题解

考虑任取一个节点为根，每个节点上存从根到该节点所有颜色及其出现次数。

直接去存数据量显然是巨大的，因此考虑用主席树维护这个东西。

接着，类似于树上差分的做法，在处理链上的信息时，我们通过几个由根到节点的路径信息相加减得到。

具体地，若链的端点为 x, y，两端 LCA 为 L，fa_L 表示 L 的父亲节点，当前所查询的区间对应编号为 p，则答案为：

tr_{x, p} + tr_{y, p} - tr_{L, p} - tr_{fa_L, p}

然后我们要求出现次数严格 > \frac{|S|}{k} 的元素，发现对于查询的每层，最多只会有 k 个节点满足条件。

然后我们对于 len \times k \le |S| 的区间直接舍去，这一部分复杂度就是 O(\sum{k} \log n) 的，得到了保证。

总复杂度为 O((n + \sum{k} + q) \log n)。 

#include <bits/stdc++.h>
#define File(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
#define rep(i, l, r) for (int i = (l), i##END = (r); i <= i##END; i ++)
#define dwn(i, r, l) for (int i = (r), i##END = (l); i >= i##END; i --)
using namespace std;

typedef long long i64;

template<typename T1, typename T2>
inline void Max(T1 &x, const T2 &k){ x = (x > k ? x : k); }
template<typename T1, typename T2>
inline void Min(T1 &x, const T2 &k){ x = (x < k ? x : k); }

namespace Xterfusion{
  const int N = 1e5 + 5, M = 75 * N;
  int ls[M], rs[M], v[M], rt[N], tot = 0, d[M];
  void build(int &x, int pl, int pr){
    x = ++ tot, v[x] = 0; if (pl == pr) return ;
    int mid = (pl + pr) >> 1;
    build(ls[x], pl, mid), build(rs[x], mid + 1, pr);
  }
  void upd(int lst, int &x, int pl, int pr, int pos){
    x = ++ tot; v[x] = v[lst] + 1;
    ls[x] = ls[lst], rs[x] = rs[lst], d[x] = d[lst];
    if (pl == pr) return d[x] = 1, void();
    int mid = (pl + pr) >> 1;
    if (pos <= mid) upd(ls[lst], ls[x], pl, mid, pos);
    else upd(rs[lst], rs[x], mid + 1, pr, pos);
    d[x] = d[ls[x]] + d[rs[x]];
  }

  int fa[N][20], dep[N], s[N];
  vector<int> G[N]; int n, q;
  void Dfs1(int x, int f){
    fa[x][0] = f; dep[x] = dep[f] + 1;
    rep(i, 1, 18) fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for (int y : G[x]) if (y != f) Dfs1(y, x);
  }
  int lca(int x, int y){
    if (dep[x] < dep[y]) swap(x, y);
    dwn(i, 18, 0) if (dep[x] - (1 << i) >= dep[y]) x = fa[x][i];
    if (x == y) return x;
    dwn(i, 18, 0) if (fa[x][i] != fa[y][i])
      x = fa[x][i], y = fa[y][i];
    return fa[x][0];
  }
  void Dfs2(int x){
    upd(rt[fa[x][0]], rt[x], 1, n, s[x]);
    for (int y : G[x]) if (y != fa[x][0]) Dfs2(y);
  }
  int sp; vector<int> res;
  void query(int p1, int p2, int p3, int p4, int pl, int pr, int k){
    int np = v[p1] + v[p2] - v[p3] - v[p4];
    if (1ll * np * k <= sp) return ;
    if (pl == pr){
      res.push_back(pl);
      return ;
    }
    int mid = (pl + pr) >> 1;
    query(ls[p1], ls[p2], ls[p3], ls[p4], pl, mid, k);
    query(rs[p1], rs[p2], rs[p3], rs[p4], mid + 1, pr, k);
  }

  void main(){
    cin >> n >> q;
    fill(d, d + tot, 0), fill(v, v + tot, 0);
    tot = 0; 
    rep(i, 1, n) cin >> s[i];
    rep(i, 1, n) G[i].clear(), rt[i] = 0;
    rep(i, 1, n - 1){
      int u, v; cin >> u >> v;
      G[u].push_back(v), G[v].push_back(u);
    }
    Dfs1(1, 0);
    build(rt[0], 1, n);
    Dfs2(1);
    while (q --){
      int x, y, k; cin >> x >> y >> k;
      int L = lca(x, y); res.clear();
      sp = dep[x] + dep[y] - dep[L] - dep[fa[L][0]];
      query(rt[x], rt[y], rt[L], rt[fa[L][0]], 1, n, k);
      if (res.empty()) cout << "-1";
      else{
        sort(res.begin(), res.end());
        for (auto v : res) cout << v << ' ';
      }
      cout << '\n';
    }
  }
}

int main(){
  #ifndef ONLINE_JUDGE
    File("data");
  #endif
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int id, T = 1; cin >> T;
  while (T --) Xterfusion::main();
  return 0;
}