题意：强制在线，求最小的 $k$ ，使得保留边权 $\leqslant k$ 的边集后 $ps$ 所在连通块有不少于 $pt$ 种颜色。

30分暴力：二分这个权值 $k$，暴力 $dfs$ 统计 $ps$ 所在连通块内的颜色数目。

复杂度是 $\mathcal{O(qn \log w)}$ 。

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define repp(i,a,b) for(int i=(a);i<(b);++i)
#define perr(i,a,b) for(int i=(a);i>(b);--i)
#define rii(x,y) ri(x), ri(y)
#define riii(x,y,z) ri(x), ri(y), ri(z)
#define rz resize
#define pb push_back
#define clr clear

using namespace std;

struct edge { int x, w; };
vector< vector<edge> > g;
vector< vector<int> > col;
vector<int> buc, stk;

int wt, v_col;


inline void ri(int &x) {
    x = 0; char ch; int f = 1;
    do { ch = getchar(); if(ch == '-') f = -1; } while( ch < '0' || ch > '9');
    do { x = (x<<3) + (x<<1) + (ch&15), ch = getchar(); } while(ch >= '0' && ch <= '9');
    x *= f;
}

vector<int> vis;
void dfs(int cur, int pre) {
    vis[cur] = v_col;
    for(int cl : col[cur]) buc[cl] = v_col;
    for(edge e : g[cur])
        if(vis[e.x] != v_col && e.w <= wt)
            dfs(e.x, cur);
}

int check(int n, int start, int weight) {
    wt = weight; ++v_col;
    dfs(start, 0);
    int ret = 0;
    for(int i : buc) if(i == v_col) ++ret;
    return ret;
}

int main() {
    int n, m, nums, a, u, v, w; rii(n, m);
    col.rz(n + 1); g.rz(n + 1);
    stk.pb(0);
    rep(i,1,n) {
        ri(nums); rep(j,1,nums) ri(a), col[i].pb(a);
    }
    rep(i,1,m) {
        riii(u, v, w);
        g[u].pb({v, w}); g[v].pb({u, w});
        stk.pb(w);
    }
    sort(stk.begin(), stk.end());
    vector<int>::iterator ed = unique(stk.begin(), stk.end());
    stk.erase(ed, stk.end());
    buc.assign(stk[stk.size()-1]+10, 0);
    vis.assign(n + 10, 0);
    int q, k; rii(q, k);
    int lastans = 0;
    rep(qr, 1, q) {
        int l = 0, r = stk.size() - 1, s, t;
        rii(s, t);
        s = (s ^ lastans) % n + 1, t = (t ^ lastans) % k + 1;
        if(check(n, s, stk[r]) < t) {
            puts("-1"); lastans = 0; continue;
        }
        while(l < r) {
            int mid = (l + r) >> 1;
            if(check(n, s, stk[mid]) >= t) r = mid;
            else l = mid + 1;
        }
        lastans = stk[l];
        printf("%d\n", stk[l]);
    }
    return 0;
}

100分做法：

考虑优化统计颜色数的过程，保留 $\leqslant k$ 边集后的极大连通块显然是原图的 kruskal 重构树上所有点权小于等于 $k$ 且父节点不存在或者权值大于 $k$ 的结点。

所以原题就等同于在 kruskal 重构树上寻找 $ps$ 代表的叶节点的深度最浅的含有颜色数大于等于 $pt$ 的子树的祖先，显然具有单调性用倍增来找。统计就转化成了在 dfs 序上数颜色数，用主席树维护一下就好了。

复杂度为 $\mathcal{O(q\log ^2 n)}$ 。

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define repp(i,a,b) for(int i=(a);i<(b);++i)
#define perr(i,a,b) for(int i=(a);i>(b);--i)
#define rii(x, y) ri(x), ri(y)
#define pb push_back
#define rz resize
#define clr clear
using namespace std;

typedef long long ll;
typedef double db;
typedef long double ldb;

inline void ri(int &x) {
    x = 0; char ch; int f = 1;
    do { ch = getchar(); if(ch == '-') f = -1; } while( ch < '0' || ch > '9' );
    do { x = (x<<3)+(x<<1)+(ch&15), ch = getchar(); } while( ch >= '0' && ch <= '9' );
    x *= f;
}

const int maxn = 1e5+10, maxm = 1e6+10, maxa = 1e5+10;

struct edges_kr {int x, y, z;} es[maxm];
vector<int> col[maxn];

vector< vector<int> > krt;
int fa[maxn<<1][25], par[maxn<<1], wt[maxn<<1];
int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }
void krt_build(int n, int m) {
    sort( es + 1, es + m + 1, [&](edges_kr &a, edges_kr &b) { return a.z < b.z; } );
    rep(i,1,(n<<1)-1) par[i] = i, wt[i] = 0;
    krt.clr(); krt.rz(n << 1);
    int cnt = n;
    rep(i,1,m) {
        int x = find(es[i].x), y = find(es[i].y), z = es[i].z;
        if(x == y) continue;
        krt[++cnt].pb(x), krt[cnt].pb(y);
        wt[cnt] = z; fa[x][0] = fa[y][0] = par[x] = par[y] = cnt;
        if(cnt == (n<<1) - 1) break;
    }
}

int dfn[maxn<<1], idfn[maxn<<1], dep[maxn<<1], siz[maxn<<1], dfs_clock;
void dfs(int cur) {
    dfn[cur] = ++dfs_clock; idfn[dfs_clock] = cur;
    dep[cur] = dep[fa[cur][0]] + 1; siz[cur] = 1;
    for(int i = 1; i < 23; ++i) fa[cur][i] = fa[fa[cur][i-1]][i-1];
    for(int ver : krt[cur]) dfs(ver), siz[cur] += siz[ver];
}

int rt[maxn<<1], ls[maxm*40], rs[maxm*40], dat[maxm*40], tot;
void ist(int &p, int pre, int lp, int rp, int x, int v) {
    p = ++tot;
    if(lp == rp) { dat[p] = dat[pre] + v; return; }
    int mid = (lp + rp) >> 1;
    if(x <= mid) rs[p] = rs[pre], ist(ls[p], ls[pre], lp, mid, x, v);
    else ls[p] = ls[pre], ist(rs[p], rs[pre], mid+1, rp, x, v);
    dat[p] = dat[ls[p]] + dat[rs[p]];
}

int qry(int p, int lp, int rp, int x) {
    if(x <= lp) return dat[p];
    int mid = (lp + rp) >> 1;
    if(x <= mid) return qry(ls[p], lp, mid, x) + dat[rs[p]];
    return qry(rs[p], mid+1, rp, x);
}

int pre[maxa];

int main() {
    int n, m, nums, a;
    rii(n, m);
    rep(i,1,n) {
        ri(nums);  rep(j,1,nums) ri(a), col[i].pb(a);
    }
    rep(i,1,m) {
        ri(es[i].x); ri(es[i].y); ri(es[i].z);
    }
    krt_build(n, m);
    dfs((n<<1)-1);
    rep(i,1,(n<<1)-1) {
        if(idfn[i] > n || col[idfn[i]].empty()) {
            rt[i] = rt[i-1]; continue;
        }
        ist(rt[i], rt[i-1], 1, (n<<1)-1, i, col[idfn[i]].size());
        for(int cl : col[idfn[i]]) {
            if(pre[cl]) ist(rt[i], rt[i], 1, (n<<1)-1, pre[cl], -1);
            pre[cl] = i;
        }
    }
    int sum = 0; rep(i,1,maxa-10) sum += (pre[i] != 0);
    int lastans = 0;
    int q, s, t, k;
    rii(q, k);
    rep(qr,1,q) {
        rii(s, t);
        s = (s ^ lastans) % n + 1, t = (t ^ lastans) % k + 1;
        if(col[s].size() >= t) {
            puts("0"); lastans = 0; continue;
        }
        if(t > sum) {
            puts("-1"); lastans = 0; continue;
        }
        per(i,23,0) {
            if(!fa[s][i]) continue;
            if(qry(rt[dfn[fa[s][i]]+siz[fa[s][i]]-1], 1, (n<<1)-1, dfn[fa[s][i]]) < t) s  = fa[s][i];
        }
        s = fa[s][0];
        printf("%d\n", wt[s]);
        lastans = wt[s];
    }
    return 0;
}

暴踩 std ：
用线段树合并 / set启发式合并能在单 $\log$ 预处理之后 $\mathcal{O(1)}$ 查询，暴踩 std 。