This is the first title of this konjaku. Please forgive me for any shortcomings ̀ ㅂ• ́)و ✧
First topic
Title Description
\(A) there are \ (n \) major cities in the state. These \ (n \) major cities are connected by \ (n-1 \) two-way roads, and each road will have A pleasure value \ (w \)\ In addition to this \ (n-1 \) road in (A \) country, there will also be A two-way conveyor between every two cities, and the pleasure value of each conveyor is \ (0 \).
Xiao \ (Z \) came to \ (A \) country. He decided to make several trips to \ (A \) country. Each trip will move from A given starting point to A given destination. Small \ (Z \) can take not only ordinary roads, but also transmission channels. Unfortunately, the cost of the conveyor is too high. Xiao \ (Z \) decided to only pass through the conveyor once per trip.
With the passage of time, this \ (n-1 \) road in \ (Z \) country is also constantly improving. Therefore, sometimes the pleasure value of all roads will XOR the previous value \ (v \) at the same time.
Small \ (Z \) defines the pleasure value of a trip, which is the exclusive or sum of the pleasure values of all sides that small \ (Z \) passes through in this trip. He wants you to tell him what is the maximum pleasure value of each trip?
You should note that the route of a tour can pass through each point or side any number of times, but it must go from the beginning to the end, and pass through the conveyor at most once; The starting point and the ending point may coincide; A journey can pass through the end halfway, but it does not end the journey.
Input format
Two integers \ (n,m \) in the first line represent the number of cities in \ (A \) country and the number of trips in small \ (Z \).
The next \ (Z-1 \) line, with three integers \ (x,y,w \) in each line, indicates that there is a road with a pleasant degree of \ (w \) between the city \ (x \) and the city \ (Y \).
The following \ (m \) lines, each of which starts with an integer \ (opt \). If \ (opt=1 \), the next two positive integers \ (x,y \) indicate that the small \ (Z \) will travel from \ (x \) to \ (Y \); If \ (opt=2 \), the next integer \ (v \) represents the pleasure value of all roads, exclusive or the previous value \ (v \).
Output format
For each query, output a line indicating the maximum pleasure value of the trip.
sample input
6 4 1 2 3 1 3 0 2 4 2 2 5 4 3 6 1 1 4 1 1 2 6 2 4 1 2 6
sample output
7 6 7
Data range
For \ (100 \)% data, meet \ (1 \ Leq n, m \ Leq 5 \) \ (\ times 10 ^ 5 \), \ (0 \ Leq W, V < 2 ^ {12} \), \ (1 \ Leq x, y \ Leq n \).
Problem solution
as soon as we saw the crazy xor, we thought we must use the \ (trie\) tree to do it (in fact, it was just said in class). Then return to this question. Let's look at the meaning of the title first. In essence, we must take the conveyor belt once (otherwise, what does he give you...), Note the starting endpoint \ (A,B \), and the intermediate endpoint \ (C,D \). So we actually go from \ (A \) to \ (C \), then take the conveyor belt from \ (C \) to \ (D \), and from \ (D \) to \ (B \). At the same time, we also know the nature of \ (xor \). The same number of \ (xor \) twice is equal to the number without \ (xor \), so \ (A \) to \ (C \) can be transformed from \ (A \) to the root node and then to \ (C \).
so the problem is essentially to find four chains from a point to the root, so that the XOR sum of the four chains is the largest, and the endpoints of two chains are fixed.
since it is \ (xor \), you must use \ (trie \) tree.
Considering the requirements of time complexity and from the root node to the endpoint, we think of initializing the XOR and sum from each node to the root node through initialization, and getting the depth (later useful).
for the sake of time complexity, we certainly can't find the largest in the tree in the process of solving
Then we think of putting all possible values into the \ (trie \) tree first, and then we can realize \ (o(n) \) when looking for it. That is, to traverse the whole tree with \ (n^{2} \), put all possible two chain \ (xor \) values into it (at the same time, an array of \ (flag \) can be opened here, and there is no need to put those that have been released). When searching, just use the \ (xor \) value from the endpoint \ (AB \) to the root to search in the \ (trie \) tree.
however... Is this the end of the question \ (? \)
note that there is another kind of operation in the title. Obviously, we don't consider the influence of the last value of all path XORs, but we can't rebuild the tree \ ((TLE warning) \) after an xor. Then we think of the nature of \ (xor \) just mentioned (only related to the parity of times), so we naturally associate it with the relationship with depth. Naturally, if the depth is different, the \ (xor \) value from \ (AB \) to the root must be xor to the previous value \ (value \), otherwise it is not necessary
but... Is this OK \ (AC \) \ (? \)
here we have another problem. After the last value of XOR, the \ (trie \) tree itself has changed, rather than simply adding \ (AB \) to the root node's value XOR. How can we distinguish this influence \ (? \)
then we naturally \ ((not at all) \) think that we just need to separate the affected \ (xor \) value from the unaffected \ (xor \) value to build the tree.
Before building the tree, we first use the properties of \ (xor \) to determine the impact of those \ (xor \) values, and record them with a two-dimensional array \ (exist \)
Then put these values into different trees according to the \ (exist \) array
Then, when searching, we only need to put it into the corresponding tree according to the difference of depth parity. One needs to use the \ (xor \) value directly to the root node, and the other needs to find an xor value.
finally attach the code of \ (AC \) \ (: \)
#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
const int Maxn=(5e5+5)*2;
const int Maxw=(1<<12)+5;
int vis[1<<24]={0},head[Maxn],nxt[Maxn],to[Maxn],val[Maxn],tot=0,depth[Maxn]={0},prexor[Maxn],key=0,n,m;
void dfs(int x,int father)
{
depth[x]=depth[father]+1;
for(int e=head[x];e;e=nxt[e])
{
int v=to[e];
if(v==father) continue;
prexor[v]=prexor[x]^val[e];
dfs(v,x);
}
}
void add(int x,int y,int w)
{
nxt[++tot]=head[x];head[x]=tot;to[tot]=y;val[tot]=w;
nxt[++tot]=head[y];head[y]=tot;to[tot]=x;val[tot]=w;
}
class Trie
{
public:
int trie[1<<24][2]={0};
int tot=0;
void insert(int val)
{
int x=0;
for(int i=(1<<12);i;i>>=1){
bool c=val&i;
if(!trie[x][c]){
trie[x][c]=++tot;
}
x=trie[x][c];
}
}
int query(int val,int x) {
int ans = 0;
for (int i = (1 << 12); i; i >>= 1) {
bool c = val & i;
if (trie[x][!c]) {
ans += i;
x = trie[x][!c];
} else x = trie[x][c];
}
return ans;
}
};
Trie t[2];
bool flag[2][5005], exist[2][5005];
void build()
{
for (int i = 1; i <= n; i++)
flag[depth[i] & 1][prexor[i]] = 1;
for (int i = 0; i < (1 << 12); i++)
for (int j = 0; j < (1 << 12); j++)
{
exist[0][i ^ j] |= ((flag[0][i] & flag[0][j]) | (flag[1][i] & flag[1][j]));
exist[1][i ^ j] |= ((flag[0][i] & flag[1][j]) | (flag[1][i] & flag[0][j]));
}
for (int i = 0; i < (1 << 12); i++)
{
if (exist[0][i])
t[0].insert(i);
if (exist[1][i])
t[1].insert(i);
}
}
int result(int u,int v)
{
int k = (depth[u] & 1) ^ (depth[v] & 1),p,q;
if(k==0) {
p = t[0].query(prexor[u] ^ prexor[v], 0);
q = t[1].query(prexor[u] ^ prexor[v] ^ key, 0);
}
else{
p = t[1].query(prexor[u] ^ prexor[v], 0);
q = t[0].query(prexor[u] ^ prexor[v] ^ key, 0);
}
return max(p,q);
}
int main() {
int x,y,w,opt,v;
cin>>n>>m;
for(int i=1;i<n;++i)
{
scanf("%d%d%d",&x,&y,&w);
add(x,y,w);
}
dfs(1,0);
build();
while(m-->0)
{
scanf("%d",&opt);
if(opt==1)
{
scanf("%d%d",&x,&y);
printf("%d\n",result(x,y));
}
else
{
scanf("%d",&v);
key=key^v;
}
}
return 0;
}