- /*
- 暴力可以 st 表维护线性基, 从而复杂度两个 log
- 实际上我们可以离线来做, 并且记录可行最右值, 就是一个 log 的了
- */
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<queue>
- #include<iostream>
- #define ll long long
- #define mmp make_pair
- #define M 300010
- using namespace std;
- int read() {
- int nm = 0, f = 1;
- char c = getchar();
- for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
- for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
- return nm * f;
- }
- int n, m, Q, p[33], q[33], ans[M], w[M], l[M], d[M];
- vector<int> note[M];
- vector<pair<int, int>> to[M];
- void dfs(int now, int f) {
- for(int i = 0; i <to[now].size(); i++) {
- int vj = to[now][i].first;
- if(vj == f) continue;
- d[vj] = d[now] ^ to[now][i].second;
- dfs(vj, now);
- }
- }
- int main() {
- n = read(), m = read(), Q = read();
- for(int i = 1; i < n; i++) {
- int vi = read(), vj = read(), v = read();
- to[vi].push_back(mmp(vj, v));
- to[vj].push_back(mmp(vi, v));
- }
- dfs(1, 0);
- for(int i = 1; i <= m; i++) w[i] = d[read()] ^ d[read()] ^ read();
- for(int i = 1; i <= Q; i++) {
- ans[i] = d[read()] ^ d[read()];
- l[i] = read();
- note[read()].push_back(i);
- }
- for(int t = 1; t <= m; t++) {
- int x = w[t], r = t;
- for(int i = 30; i>= 0; i--) {
- if((x>> i) & 1) {
- if(!p[i]) {
- p[i] = x, q[i] = r;
- break;
- }
- if(q[i] <r) swap(p[i], x), swap(q[i], r);
- x ^= p[i];
- }
- }
- for(int k = 0; k < note[t].size(); k++) {
- int v = note[t][k];
- for(int i = 30; i>= 0; i--) if(q[i]>= l[v]) ans[v] = min(ans[v], ans[v] ^ p[i]);
- }
- }
- for(int i = 1; i <= Q; i++) {
- cout << ans[i] << "\n";
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3027239.html