题目描述
给一棵含有n个结点的有根树,根结点为1,编号为i的点有点权a; (i ∈ [1,n])。现在有两种操作,格式如下:
1 x y:该操作表示将点的点权改为y。
2 x:该操作表示查询以结点x为根的子树内的所有点的点权的异或和。
现有长度为m的操作序列,请对于每个第二类操作给出正确的结果。
输入格式
输入的第一行包含两个正整数n, m,用一个空格分隔。
第二行包含n个整数a1, a2,. . . , an,相邻整数之间使用一个空格分隔。
接下来n-1行,每行包含两个正整数ui,vi,表示结点ui和vi之间有一条边。
接下来m行,每行包含一个操作。
输出格式
输出若干行,每行对应一个查询操作的答案。
对于30%的评测用例,n, m ≤ 1000;
对于所有评测用例,1 n, m < 1000000, 0 ≤ ai,y < 100000。
样例输入
4 4
1 2 3 4
1 2
1 3
2 4
2 1
1 1 0
2 1
2 2
样例输出
4
5
6
算法1
(暴力模拟) $O(nm)$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
//某些连续的入序对应树中的节点是一条链,某节点入序和出序之间对应的节点一定在子树中
const int N =1e6+10;
int w[N];
int n,m;
vector<int> g[N];
int in[N],out[N],idx; //入序和出序
int dfn[N]; //根据dfs序存储节点(即入序)
void dfs(int u,int p)
{
in[u] = ++idx;
dfn[idx] = u;
for(auto v : g[u])
{
if(v == p) continue;
dfs(v,u);
}
out[u] = idx;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<=n-1;i++)
{
int u,v;cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,-1);
while(m--)
{
int op;cin>>op;
if(op == 1)
{
int x,y;cin>>x>>y;
w[x] = y;
}
else if(op == 2)
{
int ans = 0;
int x;cin>>x;
for(int i=in[x];i<=out[x];i++)
{
ans^=w[dfn[i]];
}
cout<<ans<<'\n';
}
}
return 0;
}
算法2
(树状数组优化) $O(mlogn)$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
//某些连续的入序对应树中的节点是一条链,某节点入序和出序之间对应的节点一定在子树中
const int N =1e6+10;
int w[N];
int n,m;
vector<int> g[N];
int in[N],out[N],idx; //入序和出序
int dfn[N]; //根据dfs序存储节点(即入序)
int tr[N];
void dfs(int u,int p)
{
in[u] = ++idx;
dfn[idx] = u;
for(auto v : g[u])
{
if(v == p) continue;
dfs(v,u);
}
out[u] = idx;
}
int lowbit(int x)
{
return x&-x;
}
void add(int x,int d)
{
for(int i=x;i<=n;i+=lowbit(i))
{
tr[i] ^= d;
}
}
int sum(int x)
{
int res = 0;
for(int i=x;i>=1;i-=lowbit(i))
{
res ^= tr[i];
}
return res;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<=n-1;i++)
{
int u,v;cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,-1);
for(int i=1;i<=n;i++)
{
add(i,w[dfn[i]]);
}
while(m--)
{
int op;cin>>op;
if(op == 1)
{
int x,y;cin>>x>>y;
add(in[x],w[x]^y); //原值为w[x],w[x]^w[x]^y = y,实现了修改
}
else if(op == 2)
{
int x;cin>>x;
int ans = sum(out[x]) ^ sum(in[x] - 1);
cout<<ans<<'\n';
}
}
return 0;
}
宝宝好棒我要做这个题
不许做