题解 P6098 【[USACO19FEB]Cow Land G】

震惊,蒟蒻学树剖第二天就打题解

所以说,理解之后树剖这种东西其实难度真心不大.至少这种模板题都可以秒切的

这里推荐一个博客: 树剖详解

蒟蒻就是在这个博客上学到的

如果想看我自己写的总结,请点我的博客

这个链接(虽然这个是写给自己看的,理解难度应该不小)

树剖的方法在博客上都有了,在这里不细讲,专注讲一下这题的实现:

\(dfs\) 请使用博客上的方法,这题需要做的只是照搬

首先,我们可以发现,这题跟普通的树剖基本上一样.唯一的区别就是他要使用 \(xor\) .那么,我们发现, \(xor\) 的操作其实跟加减没有任何区别.于是,我们只需要将加减法换成 \(xor\), 这题的操作就实现了

1.update

update跟正常的线段树update没有区别,而且他不需要lazy,因为他只需要update一个点.所以我们仍然是二分查找,找到就二分,然后他的父亲就更新为左儿子 \(xor\) 右儿子.

我们还可以观察到,如果更新右儿子,那么左儿子就不用更新了.因此,这个更新速度是恒定的 \(O(logn)\)

void update(int way, int l, int r, int q, int val){

  if (q<l || q>r) return;//不在范围内(其实用处不大)

  if (l==r && r==q) {seg[way]=val;return;}//刚好是这个数就更新

  if (l==r) return;//否则不更新

  int mid = (l+r)/2;

  if (q<=mid)update(way*2,l,mid,q,val);//在左儿子的区间

  if (q>mid)update(way*2+1,mid+1,r,q,val);//在右儿子的区间

  seg[way]  =seg[way*2]^seg[way*2+1];//用儿子更新父亲

}

2.query

这题的难点来了:怎么拿路径

我们可以发现,取两点之间的路径相当于分别取两点到他俩 \(lca\) 的值.

再观察,我们发现,在取 \(lca\) 途中答案可以直接更新,因为去lca的路径只有一条,所以,我们每次query的时候先将答案设成0,每次网上跳区间的时候答案就是 \(ans^区间\)

int query_up(int way, int l, int r, int qlow, int qhigh){

  if (qlow<= l && r<=qhigh) return seg[way];//完全包围

  if (l>qhigh || r<qlow) return 0;//不在范围

  int mid = (l+r)/2;

  return (query_up(way*2,l,mid,qlow,qhigh) ^ query_up(way*2+1,mid+1,r,qlow,qhigh));//左儿子^右儿子

}

int query(int x, int y){

  int ans = 0;//设答案为0

  while(top[x]!=top[y]){//如果不在同一条链

    if (dep[top[x]]<dep[top[y]]) swap(x,y);//谁高谁低

    ans ^= query_up(1,1,n,id[top[x]],id[x]);//更新答案

    x = fat[top[x]];//跳到上面那条链

  }

  if (dep[x]>dep[y]) swap(x,y);

  ans ^= query_up(1,1,n,id[x],id[y]);//找本链的值

  return ans;

}

完整代码:

#include <iostream>

#include <algorithm>

#include <vector>

#include <fstream>

using namespace std;

const int MAXN = 1e5+5;

int res = 0;

int n,m,r,p,dep[MAXN],fat[MAXN],son[MAXN],sz[MAXN],num[MAXN],id[MAXN],top[MAXN],wt[MAXN],cnt=0,head[MAXN],tot = 0;

int seg[MAXN*4],lazy[MAXN*4];

vector<int> adj[MAXN];

void dfs1(int pos, int f, int depth){

  dep[pos] = depth;

  fat[pos] = f;

  sz[pos] = 1;

  int maxi = -1;

  for (int v : adj[pos]){

    if (v == f) continue;

    dfs1(v,pos,depth+1);

    sz[pos]+=sz[v];

    if (maxi<sz[v]) {maxi = sz[v];son[pos] = v;}

  }

}

bool vis[MAXN];

void dfs2(int pos, int top_pos){

  id[pos] = ++cnt;

  wt[cnt] = num[pos];

  top[pos] = top_pos;

  if (!son[pos]) return;

  dfs2(son[pos],top_pos);

  for (int v : adj[pos]){

    if (v==fat[pos] || v==son[pos])  continue;

    dfs2(v,v);

  }

}//树剖的基础dfs

void make_tree(int way, int l, int r){

  if (l==r) {seg[way] = wt[l];return;}

  int mid = (l+r)/2;

  make_tree(way*2,l,mid);

  make_tree(way*2+1,mid+1,r);

  seg[way] = seg[way*2] ^seg[way*2+1] ;

}//建树

void update(int way, int l, int r, int q, int val){

  if (q<l || q>r) return;

  if (l==r && r==q) {seg[way]=val;return;}

  if (l==r) return;

  int mid = (l+r)/2;

  if (q<=mid)update(way*2,l,mid,q,val);

  if (q>mid)update(way*2+1,mid+1,r,q,val);

  seg[way]  =seg[way*2]^seg[way*2+1];

}//更新

int query_up(int way, int l, int r, int qlow, int qhigh){

  if (qlow<= l && r<=qhigh) return seg[way];

  if (l>qhigh || r<qlow) return 0;

  int mid = (l+r)/2;

  return (query_up(way*2,l,mid,qlow,qhigh) ^ query_up(way*2+1,mid+1,r,qlow,qhigh));

}//求区间

int query(int x, int y){

  int ans = 0;

  while(top[x]!=top[y]){

    if (dep[top[x]]<dep[top[y]]) swap(x,y);

    ans ^= query_up(1,1,n,id[top[x]],id[x]);

    x = fat[top[x]];

  }

  if (dep[x]>dep[y]) swap(x,y);

  ans ^= query_up(1,1,n,id[x],id[y]);

  return ans;

}//求链

int main(){

  cin >> n >> m;

  for (int i=1;i<=n;i++) cin >> num[i];

  for (int i=0;i<n-1;i++){

    int a,b; cin >> a  >> b;

    adj[a].push_back(b);

    adj[b].push_back(a);

  }

  dfs1(1,0,1);

  dfs2(1,1);

  make_tree(1,1,n);

  //初始化

  for (int i=0;i<m;i++){

    int ind,a,b; cin >> ind >> a >> b;

    if (ind==1){

      update(1,1,n,id[a],b);

    }else{

      cout << query(a,b) << endl;

    }//操作

  }

}

复杂度 \(O(nlog^2n)\) 可以过

做完建议去做P3384,本蒟蒻就是做了那题才恍然大悟的

巴特西

题解 P6098 【[USACO19FEB]Cow Land G】

最新文章

热门文章