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 */