正題

P3401

---

題目大意

給你一棵樹，讓你進(jìn)行以下操作

修改一條邊的邊權(quán)

查詢一條路徑的所有子路徑異或值的和

---

解題思路

記下所有點到根節(jié)點的路徑亦或值，那么查詢就是所有點對的異或值之和

因為邊權(quán)<1024，最多只有10位，所以可以樹鏈剖分，然后統(tǒng)計每一位1的數(shù)量，最后乘起來

---

code

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 30010 using namespace std; ll n,q,x,y,z,w,sum,num,tot,v[N],vv[N],h[N],hs[N],fa[N],sz[N],dep[N],low[N],dfn[N],top[N]; struct rec {ll to,nx,l; }e[N<<1]; struct node {ll a[10];node operator +(const node &b){node c;for(ll i=0;i<10;++i)c.a[i]=a[i]+b.a[i];return c;} }; struct Tree {#define ls x*2#define rs x*2+1node s[N<<2];int lazy[N<<2];void push_up(ll x){s[x]=s[ls]+s[rs];return;}void get(ll x,ll l,ll r,ll y){lazy[x]^=y;for(int i=0;i<10;++i)if(y&(1<<i))s[x].a[i]=r-l+1-s[x].a[i];return;}void push_down(ll x,ll l,ll r){if(lazy[x]){int mid=l+r>>1;get(ls,l,mid,lazy[x]);get(rs,mid+1,r,lazy[x]);lazy[x]=0;}return;}void change(ll x,ll l,ll r,ll y,ll z){if(l==r){for(ll i=0;i<10;++i)s[x].a[i]=z&1,z>>=1;return;}ll mid=l+r>>1;if(y<=mid)change(ls,l,mid,y,z);else change(rs,mid+1,r,y,z);push_up(x);return;}void chg(ll x,ll L,ll R,ll l,ll r,ll z){if(L==l&&R==r){get(x,L,R,z);return;}ll mid=L+R>>1;push_down(x,L,R);if(r<=mid)chg(ls,L,mid,l,r,z);else if(l>mid)chg(rs,mid+1,R,l,r,z);else chg(ls,L,mid,l,mid,z),chg(rs,mid+1,R,mid+1,r,z);push_up(x);return;}node ask(ll x,ll L,ll R,ll l,ll r){if(L==l&&R==r)return s[x];ll mid=L+R>>1;push_down(x,L,R);if(r<=mid)return ask(ls,L,mid,l,r);else if(l>mid)return ask(rs,mid+1,R,l,r);else return ask(ls,L,mid,l,mid)+ask(rs,mid+1,R,mid+1,r);} }T; void add(ll x,ll y,ll z) {e[++tot].to=y;e[tot].l=z;e[tot].nx=h[x];h[x]=tot;return; } void dfs1(ll x) {sz[x]=1;for(ll i=h[x];i;i=e[i].nx){ll y=e[i].to;if(y==fa[x])continue;dep[y]=dep[x]+1;v[y]=v[x]^e[i].l;vv[y]=e[i].l;fa[y]=x;dfs1(y);sz[x]+=sz[y];if(sz[y]>sz[hs[x]])hs[x]=y;}return; } void dfs2(ll x,ll anc) {top[x]=anc;dfn[x]=++w;T.change(1,1,n,dfn[x],v[x]);if(hs[x])dfs2(hs[x],anc);for(ll i=h[x];i;i=e[i].nx){ll y=e[i].to;if(y==fa[x]||y==hs[x])continue;dfs2(y,y);}low[x]=w;return; } node ask(ll x,ll y) {node now;for(ll i=0;i<10;++i)now.a[i]=0;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);now=now+T.ask(1,1,n,dfn[top[x]],dfn[x]);x=fa[top[x]];}if(dep[x]>dep[y])swap(x,y);now=now+T.ask(1,1,n,dfn[x],dfn[y]);z=x;return now; } int main() {scanf("%lld%lld",&n,&q);for(ll i=1;i<n;++i){scanf("%lld%lld%lld",&x,&y,&z);add(x,y,z);add(y,x,z);}dep[1]=1;fa[1]=1;dfs1(1);dfs2(1,1);while(q--){scanf("%lld",&x);if(x&1){scanf("%lld%lld",&x,&y);node g=ask(x,y);sum=0;num=dep[x]-dep[z]+dep[y]-dep[z]+1;for(ll i=0;i<10;++i)sum+=(1<<i)*(num-g.a[i])*g.a[i];printf("%lld\n",sum);}else{scanf("%lld%lld%lld",&x,&y,&z);if(dep[x]<dep[y])swap(x,y);T.chg(1,1,n,dfn[x],low[x],vv[x]^z);vv[x]=z;}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【树链剖分】洛谷树（P3401）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。