题解 CF916E 【Jamie and Tree】
Farkas_W
·
·
题解
\text{前言}
$\quad$另外洛谷上还有一道关于换根操作的题目：[P3979 【遥远的国度】](https://www.luogu.com.cn/problem/P3979)([我的题解](https://www.luogu.com.cn/blog/Farkas/solution-p3979))
$$\text{关于题目要求的操作}$$
$\quad$其实可以发现在一棵树中，只有父亲(祖先)，儿子(子树)，深度等信息会因为根节点的变化而变化，所以题目一般需要你有换根操作，子树修改操作，求 $LCA$ (最近公共祖先)，我们分别来考虑一下。(可以看看下面这张图来理解，题目中的图)
)
$$\text{换根}$$
$\quad$因为每换一次根，树中的很多信息都会改变，不可能每次换根都跑两便 $dfs$ 预处理，所以我们考虑其他方法，对于单纯的换根操作，只需要设置一个全局变量 $root$ 来存储根的编号( $root$ 初始化为 $1$ ，默认以 $1$ 为根)，对于其他操作，再通过分类讨论 $root$ 的位置来进行操作。
$$\text{LCA(最近公共祖先)}$$
$\quad$因为这题我们肯定用树链剖分解题，所以对于原图( $root==1$ )的情况下 $LCA$ 的求法肯定是使用树链剖分的(~~当然如果读者愿意专门打个倍增，那么你们随意~~)
$\quad$**注意：(小写) $lca(x,y)$ 表示在以1为根的树中 $x$ 和 $y$ 的最近公共祖先，(大写) $LCA(x,y)$ 表示在以 $root$ 为根的树中 $x$ 和 $y$ 的最近公共祖先。**
```cpp
il int lca(int x,int y) //模板树链剖分求LCA
{
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
x=father[fx];fx=top[x];
}
if(dep[x]>dep[y])swap(x,y);
return x;
}
```
$\quad$接下来我们就要对 $root$ 的位置进行分类讨论了，代码先贴出来给你们看看。
```cpp
il int LCA(int x,int y)
{
if(dep[x]>dep[y])swap(x,y);
int xr=lca(x,root),yr=lca(y,root),xy=lca(x,y);
if(xy==x)
{
if(xr==x){if(yr==y)return y;return yr;}
return x;
}
if(xr==x)return x;if(yr==y)return y;
if((xr==root&&xy==yr)||(yr==root&&xy==xr))return root;
if(xr==yr)return xy;
if(xy!=xr)return xr;return yr;
}
```
$\quad$另外我们可以再画几张图来方便理解。
一.当 $lca(x,y)==x$ (可以先按深度调序， $dep[x]<=dep[y]$)
$\quad$ $1$. 情况 $1$ ：$root$ 在 $x$ 的子树中，也在 $y$ 的子树中，即 $lca(x,root)==x$ && $lca(y,root)==y$ ，此时 $LCA(x,y)$ 是 $y$ ，因为图要反过来看(以 $root$ 为根)
$\quad$ $2$. 情况 $2$ ： $root$ 在 $x$ 的子树中，但不在 $y$ 的子树中，即 $lca(x,root)$ ，此时 $LCA(x,y)$ 是 $lca(y,root)$。
$\quad$ $3$. 情况 $3$ ：其他情况下， $LCA(x,y)$ 就是 $x$ 。
二.当 $lca(x,y)!=x$ (因为 $dep[x]<=dep[y]$，所以 $lca(x,y)!=y$ ， $x$ , $y$ 在不同子树上)
$\quad$ 1. 情况1：( $lca(x,root)==x$ )||( $lca(x,root)==x$ ),root在x(或y)的子树中时， $LCA(x,y)$ 为 $x$ (或 $y$ )，显然。
$\quad$ 2. 情况2：( $lca(x,root)==root$ && $lca(x,y)==lca(y,root)$ )||( $lca(y,root)==root$ && $lca(x,y)==lca(x,root)$)，即 $root$ 在 $x$ 到 $y$ 的简单路径上时，答案为 $root$ 。(也可以用深度判断， ( $lca(x,root)===root$ && $dep[root]>=dep[lca(x,y)]$ )||( $lca(y,root)==root$ && $dep[root]>=dep[lca(x,y)]$ ))
$\quad$ 3. 情况3： $lca(x,root)==lca(y,root)$ ，即 $root$ 在上方时，$LCA(x,y)$ 为 $lca(x,y)$ 。
$\quad$ 4. 情况4：当 $root$ 在$x$，$y$ 的链上节点的子树中时， $LCA(x,y)$ 为那个链上节点。
$\quad$这样就把树上所有 $root$ 位置的情况都考虑到了，不重不漏。
$$\text{子树修改(查询)}$$
$\quad$ 情况 $1$ ：当 $x=root$ 时， $x$ 就是此时整棵树的根，那么就是全局修改(查询)。
$\quad$ 情况 $2$ ：当 $root$ 在x子树中时，就需要特别判断了，根据图像我们可以发现此时x的真正子树是包括除了 $root$ 方向上的子树之外其他所有节点。
$\quad$ 情况 $3$ ：其他情况下 $x$ 的子树以 $root$ 为根和以 $1$ 为根是一样的。
```cpp
il int find(int x,int y)//寻找x中root所在的儿子节点
{
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
if(father[fx]==y)return top[x];
x=father[fx];fx=top[x];
}
if(dep[x]>dep[y])swap(x,y);
return son[x];
}
il int query1(int x)
{
int res=0;
if(x==root){return query(1,1,n,1,n);}
if(seg[root]>=seg[x]&&seg[root]<=seg[x]+size[x]-1){//判断root在x的子树中
res+=query(1,1,n,1,n);int y=find(x,root);
res-=query(1,1,n,seg[y],seg[y]+size[y]-1);
return res;
}
return query(1,1,n,seg[x],seg[x]+size[x]-1);
}
```
$$\text{完整代码}$$
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
using namespace std;
#define int long long
#define next neee
#define re register int
#define il inline
#define inf 1e18
il int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-')ch=getchar();
if(ch=='-')f=-1,ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return x*f;}
il void print(int x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)print(x/10);
putchar(x%10+'0');}
const int N=2e5+5;
int n,m,next[N<<1],go[N<<1],head[N],tot,a[N],top[N],root;
int sum[N<<2],seg[N],rev[N],son[N],size[N],dep[N],father[N],c[N<<2];
il void Add(int x,int y)
{next[++tot]=head[x];head[x]=tot;go[tot]=y;}
il void dfs1(int x,int fa)
{
father[x]=fa;dep[x]=dep[fa]+1;size[x]=1;
for(re i=head[x],y;i,y=go[i];i=next[i])
{
if(y==fa)continue;
dfs1(y,x);
size[x]+=size[y];
if(size[y]>size[son[x]])son[x]=y;
}
}
il void dfs2(int x,int topf)
{
top[x]=topf;seg[x]=++seg[0];rev[seg[x]]=x;
if(!son[x])return;
dfs2(son[x],topf);
for(re i=head[x],y;i,y=go[i];i=next[i])
{
if(top[y])continue;
dfs2(y,y);
}
}
il void build(int k,int l,int r)
{
if(l==r){sum[k]=a[rev[l]];return;}
int mid=l+r>>1;
build(k<<1,l,mid);build(k<<1|1,mid+1,r);
sum[k]=sum[k<<1]+sum[k<<1|1];
}
il void ADD(int k,int l,int r,int v)
{sum[k]+=(r-l+1)*v;c[k]+=v;}
il void pushdown(int k,int l,int r,int mid)
{
if(l==r){c[k]=0;return;}
ADD(k<<1,l,mid,c[k]);ADD(k<<1|1,mid+1,r,c[k]);
c[k]=0;}
il void change1(int k,int l,int r,int x,int y,int z)
{
if(x<=l&&y>=r){ADD(k,l,r,z);return;}
int mid=l+r>>1;
if(c[k])pushdown(k,l,r,mid);
if(x<=mid)change1(k<<1,l,mid,x,y,z);
if(y>mid)change1(k<<1|1,mid+1,r,x,y,z);
sum[k]=sum[k<<1]+sum[k<<1|1];
}
il int query(int k,int l,int r,int x,int y)
{
if(x<=l&&y>=r)return sum[k];
int mid=l+r>>1,res=0;
if(c[k])pushdown(k,l,r,mid);
if(x<=mid)res+=query(k<<1,l,mid,x,y);
if(y>mid)res+=query(k<<1|1,mid+1,r,x,y);
return res;
}
il int lca(int x,int y)
{
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
x=father[fx];fx=top[x];
}
if(dep[x]>dep[y])swap(x,y);
return x;
}
il int LCA(int x,int y)
{
if(dep[x]>dep[y])swap(x,y);
int xr=lca(x,root),yr=lca(y,root),xy=lca(x,y);
if(xy==x){if(xr==x){if(yr==y)return y;return yr;}return x;}
if(xr==x)return x;if(yr==y)return y;
if((xr==root&&xy==yr)||(yr==root&&xy==xr))return root;if(xr==yr)return xy;
if(xy!=xr)return xr;return yr;
}
il int find(int x,int y)//寻找x中root所在的儿子节点
{
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
if(father[fx]==y)return top[x];
x=father[fx];fx=top[x];
}
if(dep[x]>dep[y])swap(x,y);
return son[x];
}
il void change2(int x,int z)
{
if(x==root){change1(1,1,n,1,n,z);return;}
if(seg[root]>=seg[x]&&seg[root]<=seg[x]+size[x]-1){//判断root在x的子树中
change1(1,1,n,1,n,z);int y=find(x,root);
change1(1,1,n,seg[y],seg[y]+size[y]-1,-z);
}
else change1(1,1,n,seg[x],seg[x]+size[x]-1,z);
}
il int query1(int x)
{
int res=0;
if(x==root){return query(1,1,n,1,n);}
if(seg[root]>=seg[x]&&seg[root]<=seg[x]+size[x]-1){//判断root在x的子树中
res+=query(1,1,n,1,n);int y=find(x,root);
res-=query(1,1,n,seg[y],seg[y]+size[y]-1);
return res;
}
return query(1,1,n,seg[x],seg[x]+size[x]-1);
}
signed main()
{
n=read();m=read();
for(re i=1;i<=n;i++)a[i]=read();
for(re i=1;i<n;i++){re x=read(),y=read();Add(x,y);Add(y,x);}
root=1;dfs1(1,0);dfs2(1,1);build(1,1,n);
while(m--)
{
re k=read();
if(k==1)root=read();
if(k==2){re x=read(),y=read(),z=read();change2(LCA(x,y),z);}
if(k==3){re x=read();print(query1(x));putchar('\n');}
}
return 0;
}
```
$\quad$码题解不易，如果觉得不错，不妨点个赞呗！