solution

首先可以发现,这张图其实可以转化为一棵最大生成树。

我们按权值从大到小加入边,如果新加入的边所连接的两点,已经可以通过其他权值更大的边相连,后面的询问中只删除这条边起不到任何作用。

所以我们考虑建出 重构树

具体建立方法:对于在生成树中的一条边,新建一个节点,并且从所在的集合分别连边。将的点权设为的边权。并将所在的集合改为。最终重构树的根节点为最后新建的节点。

重构树中,每个生成树中的节点在重构树中全都是叶子节点。生成树中两个节点之间的路径最小值为重构树中这两个点的点权。

利用这条性质,我们考虑回答询问。对于每个询问,我们如果暴力处理,可以删除这个点任意两个点路径上的最小权值,也就是在重构树上这两个点的。最后答案就是这些中权值最大值。

因为重构树上一个节点的权值小于它子树的权值。所以我们想要深度比较大的那些就行了。(感性理解一下吧,我也不知道该咋说了qwq)。所以按照dfs序排个序。然后每次查询相邻的两个点的即可。

下面来说为什么直接建立生成树是错的!

先给出一组hack数据(并不一定能hack到所有这种程序,因为排序结果和具体建数方式有关)

7 6 1
1 2 5
1 5 5
2 3 5
2 4 1
5 6 5
5 7 5
3 3 4 6

也就是下面这张图。

我们要求不能连通,按照序排序后就是的顺序。路径上的最小边是路径上的最小边是。这样我们两次计算删掉的都是这条边,而此时仍是可以互达的。然后就了。

code

/*
* @Author: wxyww
* @Date:   2020-04-24 21:17:32
* @Last Modified time: 2020-04-25 19:51:50
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 1000010,logN = 20;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
struct node {
    int u,v,w;
}a[N];
bool cmp(const node &A,const node &B) {
    return A.w > B.w;
}

vector<int>e[N];

int S[N],w[N],id[N],fa[N];
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void uni(int x,int y,int k) {
    x = x,y = y;
    if(rand() & 1) swap(x,y);
    fa[x] = y;

    S[y] = k;
}
int tot,cnt;
int dep[N],lca[N][logN + 2];
void dfs(int u) {
    id[u] = ++cnt;

    for(int i = 1;i <= logN; ++i) {
        lca[u][i] = lca[lca[u][i - 1]][i - 1];
    }

    for(vector<int>::iterator it = e[u].begin();it != e[u].end();++it) {
        lca[*it][0] = u;
        dep[*it] = dep[u] + 1;
        dfs(*it);
    }
}

int LCA(int x,int y) {
    if(dep[x] < dep[y]) swap(x,y);
    for(int i = logN;i >= 0;--i) {
        if(dep[lca[x][i]] >= dep[y]) {
            x = lca[x][i];
        }
    }
    for(int i = logN;i >= 0;--i) {
        if(lca[x][i] != lca[y][i])
            x = lca[x][i],y = lca[y][i];
    }
    if(x != y) x = lca[x][0];
    return x;
}
int tmp[N];
bool cmp2(int x,int y) {
    return id[x] < id[y];
}
int main() {
    int n = read(),m = read(),Q = read();
    for(int i = 1;i <= m;++i) {
        int u = read(),v = read(),w = read();
        a[i].u = u;a[i].v = v;a[i].w = w;
    }

    sort(a + 1,a + m + 1,cmp);
    for(int i = 1;i <= n;++i) fa[i] = i,S[i] = i;
    tot = n;
    for(int i = 1;i <= m;++i) {
        int u = a[i].u,v = a[i].v;
        u = find(u),v = find(v);
        if(u != v) {
            ++tot;
            // printf("%d %d\n%d %d\n",tot,S[u],tot,S[v]);
            e[tot].push_back(S[u]);
            e[tot].push_back(S[v]);
            w[tot] = a[i].w;
            uni(u,v,tot);
        }
    }

    dfs(tot);
    int lst = 0;
    while(Q--) {
        int k = read();
        for(int i = 1;i <= k;++i) tmp[i] = read() ^ lst;
        sort(tmp + 1,tmp + k + 1,cmp2);
        lst = 0;
        for(int i = 2;i <= k;++i) {
            printf("%d %d\n",tmp[i - 1],tmp[i]);
            lst = max(lst,w[LCA(tmp[i - 1],tmp[i])]);
        }
        printf("%d\n",lst);
    }
    return 0;
}

/*

7 6 1
1 2 5
1 5 5
2 3 5
2 4 1
5 6 5
5 7 5
3 3 4 6
*/