Codeforces

Luogu

分析

一道练习分类讨论能力的好题...

假设当前的根是 $rt$ 。


首先考虑怎么求出 $rt$ 为根时 $u,v$ 的 $lca$ 。

设 $x$ 为 $1$ 为根时 $u,v$ 的 $lca$ ,$y$ 为 $1$ 为根时 $u,rt$ 的 $lca$ ,$z$ 为 $1$ 为根时 $v,rt$ 的 $lca$ 。

可以发现 $rt$ 为根时 $u,v$ 的 $lca$ 就是 $x,y,z$ 中深度最大的那个。


子树修改和子树查询类似,考虑一下修改的范围。假设当前要修改的是 $u$ 的子树。

  • 如果 $u=rt$ ,那么直接修改整棵树 。
  • 如果 $rt$ 是 $u$ 的祖先,那么直接修改 $u$ 子树 。
  • 如果 $u$ 是 $rt$ 的祖先,那么先找到 $u$ 的一个儿子 $s$ 使得 $rt$ 在 $s$ 的子树中,然后把整棵树加上 $w$ 再把 $s$ 子树减去 $w$ 即可。

具体维护可以使用线段树。具体实现及细节见代码。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=300000+10;

int n,Q,rt;
ll w[N];

struct edge { int v,nxt; } e[N<<1];
int head[N];

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int dep[N],f[19][N];
int dfn[N],low[N],rl[N],tim=0;

inline void dfs(int u,int fa) {
    dfn[u]=++tim,rl[tim]=u,dep[u]=dep[fa]+1,f[0][u]=fa;
    for (re int i=1;i<=18;++i)
        f[i][u]=f[i-1][f[i-1][u]];
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa) dfs(e[i].v,u);
    low[u]=tim;
}

#define ls (o<<1)
#define rs (o<<1|1)
ll sumv[N<<2],addv[N<<2];
inline void pushup(int o) { sumv[o]=sumv[ls]+sumv[rs]; }
inline void pushdown(int o,int l,int r) {
    if (addv[o]) {
        int mid=(l+r)>>1;
        addv[ls]+=addv[o],addv[rs]+=addv[o];
        sumv[ls]+=addv[o]*(mid-l+1),sumv[rs]+=addv[o]*(r-mid);
        addv[o]=0;
    }
}
inline void build(int o,int l,int r) {
    if (l==r) { sumv[o]=w[rl[l]],addv[o]=0; return; }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(o);
}
inline void modify(int o,int l,int r,int ql,int qr,int v) {
    if (ql<=l&&r<=qr) { sumv[o]+=1ll*v*(r-l+1),addv[o]+=v; return; }
    int mid=(l+r)>>1; pushdown(o,l,r);
    if (ql<=mid) modify(ls,l,mid,ql,qr,v);
    if (qr>mid) modify(rs,mid+1,r,ql,qr,v);
    pushup(o);
}
inline ll query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return sumv[o];
    int mid=(l+r)>>1; ll res=0; pushdown(o,l,r);
    if (ql<=mid) res+=query(ls,l,mid,ql,qr);
    if (qr>mid) res+=query(rs,mid+1,r,ql,qr);
    pushup(o); return res;
}
#undef ls
#undef rs

inline int getlca1(int u,int v) {
    if (dep[u]<dep[v]) swap(u,v);
    for (re int i=18;~i;--i)
        if (dep[f[i][u]]>dep[v]) u=f[i][u];
    if (dep[u]!=dep[v]) u=f[0][u];
    for (re int i=18;~i;--i)
        if (f[i][u]!=f[i][v]) u=f[i][u],v=f[i][v];
    if (u!=v) u=f[0][u];
    return u;
}
inline int getlca(int u,int v) {
    int x=getlca1(u,v),y=getlca1(u,rt),z=getlca1(v,rt);
    if (dep[y]>dep[x]) x=y;
    if (dep[z]>dep[x]) x=z;
    return x;
}

inline int jump(int u,int anc) {
    for (re int i=18;~i;--i)
        if (dep[f[i][u]]>dep[anc]) u=f[i][u];
    return u;
}

inline void operator_1() { rt=read(); }
inline void operator_2() {
    int u=read(),v=read(),x=read(),p=getlca(u,v);
    if (p==rt) modify(1,1,n,1,n,x);
    else if (dfn[rt]<dfn[p]||dfn[rt]>low[p])
        modify(1,1,n,dfn[p],low[p],x);
    else {
        int s=jump(rt,p);
        modify(1,1,n,1,n,x),modify(1,1,n,dfn[s],low[s],-x);
    }
}
inline void operator_3() {
    int u=read();
    if (u==rt) printf("%lld\n",query(1,1,n,1,n));
    else if (dfn[rt]<dfn[u]||dfn[rt]>low[u])
        printf("%lld\n",query(1,1,n,dfn[u],low[u]));
    else {
        int s=jump(rt,u);
        printf("%lld\n",query(1,1,n,1,n)-query(1,1,n,dfn[s],low[s]));
    }
}

int main() {
    n=read(),Q=read();
    for (re int i=1;i<=n;++i) w[i]=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    rt=1,dfs(1,0); build(1,1,n);
    while (Q--) {
        int op=read();
        if (op==1) operator_1();
        else if (op==2) operator_2();
        else operator_3();
    }
    return 0;
}
最后修改:2019 年 10 月 17 日 09 : 17 PM