[LUOGU3401]洛谷树

题目

题目背景

萌哒的Created equal小仓鼠种了一棵洛谷树！

（题目背景是辣鸡小仓鼠乱写的QAQ）。

题目描述

树是一个无环、联通的无向图，由n个点和n-1条边构成。树上两个点之间的路径被定义为他们之间的唯一一条简单路径——显然这是一条最短路径。

现在引入一个概念——子路径。假设树上两个点p1和pn之间的路径是P=<p1,p2,p3,…,pn>，那么它的子路径被定义为某一条路径P’，满足P’=<pi,pi+1,pi+2,…,pj>，其中1<=i<=j<=n。显然，原路径是一条子路径，任意一个点也可以作为子路径。

我们给每条边赋予一个边权。萌萌哒的Sugar问小仓鼠：对于任意两个点u和v，你能快速求出，u到v的路径上所有子路径经过的边的边权的xor值的和是多少。具体地说就是，你把u到v的路径上所有子路径全部提出来，然后分别把每个子路径上经过的边的边权xor在一起，最后求出得到的所有xor值的和。

什么？你不知道xor？那就去百度啊！

这时候，fjzzq2002大爷冒了粗来：窝还要你滋磁修改某条边边权的操作！

小仓鼠那么辣鸡，当然不会做这道题啦。于是他就来向你求救！

输入输出格式

输入格式：

第一行两个正整数n和q，表示点的个数，查询和询问的总次数。

接下来n-1行，每行两个正整数u、v、w，表示u和v两个点之间有一条边权为w的边。

接下来q行，格式为1 u v或2 u v w。如果为1 u v操作，你需要输出u到v的路径上所有子路径经过的边的边权的xor值的和是多少；如果为2 u v w操作，你需要把u到v这条边的边权改为w，保证这条边存在。

输出格式：

对于每个1操作，输出答案。

输入输出样例

输入样例#1：

输出样例#1：

14
26

说明

本题时限1s，内存限制128M，因新评测机速度较为接近NOIP评测机速度，请注意常数问题带来的影响。

【数据范围】

No	$n$	$q$	备注
$1$	$100$	$5$	无
$2$	$100$	$20$	无
$3$	$100$	$100$	无
$4$	$5000$	$1000$	无
$5$	$5000$	$2000$	无
$6$	$5000$	$3000$	无
$7$	$10000$	$10000$	第$i$条边连接第$i$个点和第$i+1$个点，且没有$2$操作
$8$	$10000$	$20000$	第$i$条边连接第$i$个点和第$i+1$个点，且没有$2$操作
$9$	$10000$	$10000$	第$i$条边连接第$i$个点和第$i+1$个点
$10$	$10000$	$20000$	第$i$条边连接第$i$个点和第$i+1$个点
$11$	$10000$	$10000$	没有$2$操作
$12$	$10000$	$20000$	没有$2$操作
$13$	$20000$	$20000$	没有$2$操作
$14$	$30000$	$30000$	没有$2$操作
$15$	$30000$	$10000$	无
$16$	$20000$	$20000$	无
$17$	$20000$	$20000$	无
$18$	$30000$	$20000$	无
$19$	$20000$	$30000$	无
$20$	$30000$	$30000$	无

对于100%的数据，所有边权小于等于1023。

题解

先不考虑修改操作，因为题目要求$XOR$，所以可以想到维护点$i$到根的路径的$XOR$和$sum_i$，这样$XOR_{i,j}=XOR_{rt,i}\oplus XOR_{rt,j}$

所以求两个点之间路径的$XOR$和可以按位树剖，看$sum_i$的每一位是$1$还是$0$，如果$sum_i,sum_j$这一位不同就能产生贡献

但是题目要求的是一段路径上的子路径$XOR$和的和，所以对于每一位，可以统计这段路径上面$sum$这一位是$1$的个数$num_1$，这一位是$0$的个数$num_0$，则这段路径第$k$位对答案的贡献为$num_0\times num_1\times 2^k$

如果加入修改操作了呢？

考虑修改操作影响了什么，对于点$x$的修改，会使点$x$的子树中每个点的$sum$发生改变

对于每一位，如果修改值$d$的二进制在这一位等于原来的值$w_x$，则相当于没有操作；如果不相等，就相当于$x$子树的$sum$这一位取反（由奇变偶或有偶变奇），就是一个子树取反操作

注意答案要开long long

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl (k<<1)
# define tr (k<<1|1)
# define mid (l+r>>1)
# define LL long long
using namespace std;
const int MAX=3e5+5;
struct p{
	int x,_x;
	bool tag;
}s[11][MAX<<2];
struct q{
	int x,y,dis;
}c[MAX<<1];
int n,m,num=1,cnt;
int h[MAX],w[MAX],d[MAX],f[MAX],siz[MAX],re[MAX],sum[MAX],son[MAX],top[MAX],id[MAX];
p operator+ (p a,p b)
{
	p c;
	c.x=a.x+b.x,c._x=a._x+b._x;
	return c;
}
int read()
{
	int x(0);
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x;
}
void add()
{
	int x=read(),y=read(),w=read();
	c[++num]=(q){h[x],y,w},h[x]=num;
	c[++num]=(q){h[y],x,w},h[y]=num;
}
void dfs(int x=1,int fa=0)
{
	f[x]=fa,d[x]=d[fa]+(siz[x]=1);
	for(int i=h[x];i;i=c[i].x)
	  if(c[i].y^fa)
	  {
	  	sum[c[i].y]=sum[x]^c[i].dis,dfs(c[i].y,x),siz[x]+=siz[c[i].y];
	  	if(siz[son[x]]<siz[c[i].y]) son[x]=c[i].y;
	  }
}
void dfs1(int x=1,int tp=1)
{
	top[x]=tp,id[x]=++cnt,re[cnt]=x;
	if(!son[x]) return;
	dfs1(son[x],tp);
	for(int i=h[x];i;i=c[i].x)
	  if((c[i].y^f[x])&&(c[i].y^son[x])) dfs1(c[i].y,c[i].y);
}
p pus(p b,p c,bool Tag=0)
{
	p a;
	a.x=b.x+c.x,a._x=b._x+c._x;
	return a.tag=Tag,a;
}
void build(int l,int r,int k,int o,p *s)
{
	if(l==r)
	{
		if(sum[re[l]]&(1<<o)) s[k].x=1;
		else s[k]._x=1;
		return;
	}
	build(l,mid,tl,o,s),build(mid+1,r,tr,o,s),s[k]=pus(s[tl],s[tr]);
}
void _BUILD()
{
	for(int i=0;i<=10;++i)
	  build(1,n,1,i,s[i]);
}
void down(int k,p *s)
{
	if(!s[k].tag) return;
	s[k].tag=0,s[tl].tag^=1,s[tr].tag^=1,swap(s[tl].x,s[tl]._x),swap(s[tr].x,s[tr]._x);
}
void change(int l,int r,int k,int L,int R,p *s)
{
	if(l==L&&r==R)
	{
		swap(s[k].x,s[k]._x);
		return void(s[k].tag^=1);
	}
	down(k,s);
	if(R<=mid) change(l,mid,tl,L,R,s);
	else if(L>mid) change(mid+1,r,tr,L,R,s);
	else change(l,mid,tl,L,mid,s),change(mid+1,r,tr,mid+1,R,s);
	s[k]=pus(s[tl],s[tr],s[k].tag);
}
void _CHANGE(int x,int dis)
{
	for(int i=0;i<=10;++i)
	  if((w[x]&(1<<i))!=(dis&(1<<i))) change(1,n,1,id[x],id[x]+siz[x]-1,s[i]);
	w[x]=dis;
}
p ask(int l,int r,int k,int L,int R,p *s)
{
	if(l==L&&r==R) return s[k];
	down(k,s);
	if(R<=mid) return ask(l,mid,tl,L,R,s);
	if(L>mid) return ask(mid+1,r,tr,L,R,s);
	return ask(l,mid,tl,L,mid,s)+ask(mid+1,r,tr,mid+1,R,s);
}
p ASK(int x,int y,p *s)
{
	p ans=(p){0,0};
	while(top[x]^top[y])
	{
		if(d[top[x]]<d[top[y]]) swap(x,y);
		ans=ans+ask(1,n,1,id[top[x]],id[x],s),x=f[top[x]];
	}
	if(d[x]>d[y]) swap(x,y);
	return ans+ask(1,n,1,id[x],id[y],s);
}
LL _ASK(int x,int y)
{
	LL ans=0;
	for(int i=0;i<=10;++i)
	  {
	  	p tt=ASK(x,y,s[i]);
	  	ans+=1ll*tt.x*tt._x*(1ll<<i);
	  }
	return ans;
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<n;++i,add());
	dfs(),dfs1(),_BUILD();
	for(int i=2,x,y;i<=num;i+=2)
	  {
	  	x=c[i].y,y=c[i^1].y;
	  	if(d[x]<d[y]) swap(x,y);
	  	w[x]=c[i].dis;
	  }
	for(int i=1,op,u,v,w;i<=m;++i)
	  {
	  	op=read(),u=read(),v=read();
	  	if(op==1) printf("%lld\n",_ASK(u,v));
	  	else if(op==2)
	  	{
	  		if(d[u]<d[v]) swap(u,v);
			_CHANGE(u,read());
		}
	  }
	return 0;
}

题目