牛客练习赛58 F-XOR TREE（结论+树链剖分+线段树）
链接：https://ac.nowcoder.com/acm/contest/4090/F
来源：牛客网
XOR TREE
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
给出一颗n{n}n个结点n−1{n-1}n−1条边的带权树，第i{i}i个结点的权值为aia_{i}ai 。
定义点u{u}u到点v{v}v的路径的长度为点u{u}u到点v{v}v的最短路径上的所有结点的权值的异或和。
单独一个点不算做路径。
现在要求你维护q{q}q个操作：
1{1}1 u{u}u x{x}x将点u{u}u的权值修改为x{x}x
2{2}2 u{u}u v{v}v求点u{u}u到点v{v}v之间的所有子路径的长度的异或和
输入描述:
第一行两个整数n,q{n,q}n,q
第二行n个整数表示a1,a2...an{a_{1},a_{2}...a_{n}}a1,a2...an
接下来n-1行每行两个整数ui,vi{u_{i},v_{i}}ui,vi表示ui,vi{u_{i},v_{i}}ui,vi之间有一条边
接下来q行每行三个整数表示一个查询,数据保证对于查询2{2}2，满足u!=v{u!=v}u!=v。
输出描述:
对于每个查询2{2}2输出一行一个整数表示答案
示例1
输入
5 3
1 2 3 4 5
1 2
2 3
3 4
4 5
2 1 5
1 2 8
2 1 5
输出
[复制](javascript:void(0)😉
6
12
说明
让f(u,v){f(u,v)}f(u,v)表示点u{u}u到点v{v}v最短路径上所有结点的权值的异或和，那么第一个查询的答案为：
f(1,2)⨁f(1,3)⨁f(1,4)⨁f(1,5)⨁f(2,3)⨁f(2,4)⨁f(2,5)⨁f(3,4)⨁f(3,5)⨁f(4,5)=6{f(1,2)\bigoplus f(1,3)\bigoplus f(1,4)\bigoplus f(1,5)\bigoplus f(2,3)\bigoplus f(2,4)\bigoplus f(2,5)\bigoplus f(3,4)\bigoplus f(3,5)\bigoplus f(4,5)=6}f(1,2)⨁f(1,3)⨁f(1,4)⨁f(1,5)⨁f(2,3)⨁f(2,4)⨁f(2,5)⨁f(3,4)⨁f(3,5)⨁f(4,5)=6
其中f(1,4)=1⨁2⨁3⨁4,f(2,5)=2⨁3⨁4⨁5{f(1,4)=1\bigoplus 2\bigoplus 3\bigoplus 4,f(2,5)=2\bigoplus 3\bigoplus 4\bigoplus 5}f(1,4)=1⨁2⨁3⨁4,f(2,5)=2⨁3⨁4⨁5,其它的类似。
备注:
1<=u,v<=n,q<=2e5
1<=ai，x<=1e9
思路：
考虑到异或的性质\(x\oplus x=0\)，即一个数异或两次就会相消
经过分析路径中每一个点对答案的贡献发现：
- 如果路径的长度是奇数个点，那么等效于所有偶数次序的点被记录一次
- 如果路径长度是偶数个点，那么所有点都被计入一次
每一个节点的奇偶次序可以用有根树的节点深度的奇偶来表示。
那么我们不妨建立2个基于节点的dfs序的线段树，
分别为只维护深度为偶数的节点权值，（即奇数节点权值为0），不妨称为A树,
和维护深度为奇数的节点权值，（即偶数节点权值为0），不妨称为B树.
对于每一个询问：
如果路径链中有偶数个节点，则答案为A树上的路径答案异或上B树上的路径答案。
如果路径链中有奇数个节点，则答案为A树上的路径答案或B树上的路径答案，具体是哪个树上的要根据端点的奇偶性判断。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#include <sstream>
#include <bitset>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
ll poww(ll a, ll b) { if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a ;} a = a * a ; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
const int maxn = 200010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int n, m;
int root;
int a[maxn];// 鲁玫脢录碌茫脠篓
int wt[maxn];// 脨脗陆篓卤脿潞脜碌茫脠篓隆拢
int cnt;// 卤脿潞脜脫脙碌脛卤盲脕驴
int top[maxn];// 脣霉脭脷脰脴脕麓碌脛露楼碌茫卤脿潞脜
int id[maxn];//陆脷碌茫碌脛脨脗卤脿潞脜隆拢
std::vector<int> son[maxn];
int SZ[maxn];// 脳脫脢媒麓贸脨隆
int wson[maxn];// 脰脴露霉脳脫
int fa[maxn];// 赂赂陆脷碌茫
int dep[maxn];// 陆脷碌茫碌脛脡卯露脠
void dfs1(int id, int pre, int step) // 脦卢禄陇鲁枚sz,wson,fa,dep
{
dep[id] = step;
fa[id] = pre;
SZ[id] = 1;
int maxson = -1;
for (auto x : son[id])
{
if (x != pre)
{
dfs1(x, id, step + 1);
SZ[id] += SZ[x];
if (SZ[x] > maxson)
{
maxson = SZ[x];
wson[id] = x;
}
}
}
}
//麓娄脌铆鲁枚top[],wt[],id[]
void dfs2(int u, int topf)
{
id[u] = ++cnt;
wt[cnt] = a[u];
top[u] = topf;
if (!wson[u]) // 脙禄露霉脳脫脢卤脰卤陆脫陆谩脢酶
{
return ;
}
dfs2(wson[u], topf); // 脧脠麓娄脌铆脰脴露霉脳脫
for (auto x : son[u])
{
if (x == wson[u] || x == fa[u]) //脰禄麓娄脌铆脟谩露霉脳脫
{
continue;
}
dfs2(x, x); // 脙驴赂枚脟谩露霉脳脫脪脭脳脭录潞脦陋top
}
}
int lca(int x, int y) {
for (; top[x] != top[y]; dep[top[x]] > dep[top[y]] ? x = fa[top[x]] : y = fa[top[y]]);
return dep[x] < dep[y] ? x : y;
}
int dist(int x, int y) {
int l = lca(x, y);
return dep[x] + dep[y] - 2 * dep[l];
}
struct node
{
int l, r;
int val;
} A[maxn << 2], B[maxn << 2];
void build(node *segment_tree, int rt, int l, int r)
{
segment_tree[rt].l = l;
segment_tree[rt].r = r;
if (l == r)
{
return ;
}
int mid = (l + r) >> 1;
build(segment_tree, rt << 1, l, mid);
build(segment_tree, rt << 1 | 1, mid + 1, r);
}
void pushup(node *segment_tree, int rt)
{
segment_tree[rt].val = segment_tree[rt << 1].val ^ segment_tree[rt << 1 | 1].val;
}
void modify(node *segment_tree, int rt, int key, int x)
{
if (segment_tree[rt].l == key && segment_tree[rt].r == key)
{
segment_tree[rt].val = x;
return ;
}
int mid = (segment_tree[rt].l + segment_tree[rt].r) >> 1;
if (key <= mid)
{
modify(segment_tree, rt << 1, key, x);
} else {
modify(segment_tree, rt << 1 | 1, key, x);
}
pushup(segment_tree, rt);
}
int query(node *segment_tree, int rt, int l, int r)
{
if (l <= segment_tree[rt].l && segment_tree[rt].r <= r)
{
return segment_tree[rt].val;
}
int mid = segment_tree[rt].l + segment_tree[rt].r >> 1;
int res = 0;
if (r > mid)
{
res ^= query(segment_tree, rt << 1 | 1, l, r);
}
if (l <= mid)
{
res ^= query(segment_tree, rt << 1, l, r);
}
return res;
}
int qrange(node *segment_tree, int x, int y)
{
int ans = 0;
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]])
{
swap(x, y);
}
ans ^= query(segment_tree, 1, id[top[x]], id[x]);
x = fa[top[x]];
}
if (dep[x] > dep[y])
swap(x, y);
ans ^= query(segment_tree, 1, id[x], id[y]);
return ans;
}
int main()
{
// freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);
// freopen("D:\\common_text\\code_stream\\out.txt","w",stdout);
n = readint();
m = readint();
repd(i, 1, n)
{
a[i] = readint();
}
int u, v;
repd(i, 2, n)
{
u = readint();
v = readint();
// cin >> u >> v;
son[u].pb(v);
son[v].pb(u);
}
root = 1;
dfs1(root, 0, 1);
dfs2(root, root);
// build(1, 1, n);
int op, x, y;
build(A, 1, 1, n);
build(B, 1, 1, n);
repd(i, 1, n)
{
if (dep[i] & 1)
{
modify(A, 1, id[i], a[i]);
} else
{
modify(B, 1, id[i], a[i]);
}
}
while (m--)
{
op = readint();
x = readint();
y = readint();
if (op == 1)
{
if (dep[x] & 1)
{
modify(A, 1, id[x], y);
} else
{
modify(B, 1, id[x], y);
}
} else if (op == 2)
{
int d = dist(x, y);
int ans = 0;
if (d & 1)
{
ans = qrange(A, x, y)^qrange(B, x, y);
} else
{
if (dep[x] & 1)
{
ans = qrange(B, x, y) ;
} else
{
ans = qrange(A, x, y);
}
}
printf("%d\n", ans );
}
}
return 0;
}
京公网安备 11010502036488号