小清新数据结构题

链接：https://www.luogu.org/problemnew/show/P3676

题解：

看暴力：每次修改只会影响到它到1的链，询问也是它到1的链

那么考虑用树链剖分变成dfs序

链剖都想了那就考虑用线段树维护这个dfs序上的信息

维护dfs序上每个点子树的val和的平方和

修改？

假设修改 $u$

$u$

根据暴力推一下， $s s ， f f$

$s s ， f f$

代码：

#include <bits/stdc++.h>
using namespace std;
#define maxn 210000
struct{
    int a,b;
}a[maxn*2];
struct{
    int h,t,x1,x2,lazy;
}p[maxn*4];
int num,m,n,l;
int v[maxn],size[maxn],real2[maxn],
top[maxn],id[maxn],head[maxn],dep[maxn],
fa[maxn],son[maxn],x1[maxn],x2[maxn];
void arr(int x,int y)
{
    a[++l].a=head[x];
    a[l].b=y;
    head[x]=l;
}
void dfs1(int x,int y)
{
    fa[x]=y; dep[x]=dep[y]+1;
    son[x]=-1; size[x]=1;
    int u=head[x];
    while (u)
    {
        int v=a[u].b;
        if (v!=y)
        {
            dfs1(v,x);
            size[x]+=size[v];
            if (son[x]!=-1||
            size[son[x]]<size[v])
            son[x]=v;
        }
        u=a[u].a;
    }
}
void dfs2(int x,int y)
{
    top[x]=y; num++;
    id[x]=num; real2[num]=x;
    if (son[x]==-1) return;
    dfs2(son[x],y);
    int u=head[x];
    while (u)
    {
        int v=a[u].b;
        if (v!=fa[x]&&v!=son[x])
          dfs2(v,v);
        u=a[u].a;
    }
}
void dfs3(int x)
{
    int u=head[x];
    x1[id[x]]=v[x];
    while (u)
    {
        int v=a[u].b;
        if (v!=fa[x])
        { 
          dfs3(v);
          x1[id[x]]+=x1[id[v]];
        }
        u=a[u].a;
    }
    x2[id[x]]=pow(x1[id[x]],2);
}
#define mid (p[x].h+p[x].t)/2
void updata(int x)
{
    p[x].x1=p[x*2].x1+p[x*2+1].x1;
    p[x].x2=p[x*2].x2+p[x*2+1].x2;
}
void build(int x,int h,int t)
{
    p[x].h=h; p[x].t=t;
    if (h==t)
    {
        p[x].x1=x1[h];
        p[x].x2=x2[h];
        return;
    }
    build(x*2,h,mid); build(x*2+1,mid+1,t);
    updata(x); 
}
void down(int x)
{
    if (!p[x].lazy) return;
    if (p[x].h!=p[x].t)
    {
        p[x*2].lazy+=p[x].lazy;
        p[x*2+1].lazy+=p[x].lazy;
    }
    p[x].x2+=p[x].x1*2*p[x].lazy+
    (p[x].t-p[x].h+1)*p[x].lazy*p[x].lazy;
    p[x].x1+=p[x].lazy*(p[x].t-p[x].h+1);
    p[x].lazy=0;
}
void change2(int x,int h,int t,int sum)
{
    down(x);
    if (p[x].t<h||p[x].h>t) return;
    if (h<=p[x].h&&p[x].t<=t)
    {
        p[x].lazy=sum; down(x);
        return;
    }
    change2(x*2,h,t,sum);
    change2(x*2+1,h,t,sum);
    updata(x);
}
int query1(int x,int h,int t)
{
    down(x);
    if (p[x].t<h||p[x].h>t) return(0);
    if (h<=p[x].h&&p[x].t<=t)
    {
        return(p[x].x1); 
    } 
    return(query1(x*2,h,t)+query1(x*2+1,h,t));
}
int query2(int x,int h,int t)
{
    down(x);
    if (p[x].t<h||p[x].h>t) return(0);
    if (h<=p[x].h&&p[x].t<=t)
    {
        return(p[x].x2); 
    } 
    return(query2(x*2,h,t)+query2(x*2+1,h,t));
}
void change(int x,int y)
{
    int f1=top[x];
    while (true)
    {
        change2(1,id[f1],id[x],y);
        if (f1==1) return;
        x=fa[f1]; f1=top[x];
    }
}
int query(int x)
{
    int f1=top[x],tmp=0;
    while (true)
    {
        tmp+=query1(1,id[f1],id[x]);
        if (f1==1) return(tmp);
        x=fa[f1]; f1=top[x];
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n>>m;
    int c,d,e;
    for (int i=1;i<=n-1;i++)
    {
        cin>>c>>d;
        arr(c,d); arr(d,c);
    }
    for (int i=1;i<=n;i++)
      cin>>v[i];
    dfs1(1,0); dfs2(1,1); dfs3(1);
    build(1,1,n);
    for (int i=1;i<=m;i++)
    {
        cin>>c;
        if (c==1)
        {
            cin>>d>>e;
            change(d,e-v[d]);
            v[d]=e;
        }
        if (c==2)
        {
            cin>>d;
            int x=query1(1,1,1),
                y=query2(1,1,n),
                z=query(d)-x;
            cout<<y+x*x*(dep[d]-1)-2*x*z<<endl;
        }
    }
    return 0;
}

View Code

这题的难点主要在于换根操作

分析出上面的式子后就简单了