Nowcoder练习赛26 E 树上路径

2018-09-07 21:09:15


题意:一棵树,支持三种操作:

  • 子树加上一个值

  • 路径加上一个值

  • 询问一条路径上任取两个数的乘积的总和


前两个操作好办,就是树剖模板

第三个操作让我联想到了P4247 序列操作

但是因为序列转移到了树上,所以没法直接套用

那不会是LCT吧?应该不是。。

其实很简单,我们只要树剖之后线段树维护区间总和区间平方和就好了

因为最后的答案可以进行化简

比如说区间长度为3,三个数分别为 $a,b,c$

那么所求答案为 $ab+ac+bc$

经过一波操作可以发现ta其实是 $[(a+b+c)^2-a^2-b^2-c^2]/2$

其他情况同理

然后只要注意 $pushdown$ 的时候区间加法对子区间的影响就好了

还是Jan神NB啊 orzorz

贴上代码(取模不到位还WA了两发)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
typedef long long ll;
const int N=1e5+5,mod=1e9+7,inv2=5e8+4;
struct node
{
    int to,nxt;
}edge[N<<1];
int n,m,num,head[N],fa[N],son[N],dep[N],tot[N];
int cnt,idx[N],top[N],a[N],w[N];
ll sum1[N<<2],sum2[N<<2],tag[N<<2];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void add_edge(int from,int to)
{
    edge[++num]=(node){to,head[from]};
    head[from]=num;
}
void dfs(int k,int father,int deep)
{
    int bigson=0;
    fa[k]=father; dep[k]=deep; tot[k]=1;
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (v==father) continue;
        dfs(v,k,deep+1); tot[k]+=tot[v];
        if (bigson<tot[v]) bigson=tot[v],son[k]=v;
    }
}
void dfs(int k,int tp)
{
    idx[k]=++cnt; top[k]=tp; a[cnt]=k;
    if (!son[k]) return; dfs(son[k],tp);
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (!idx[v]) dfs(v,v);
    }
}
inline void pushup(int now)
{
    sum1[now]=(sum1[now<<1]+sum1[now<<1|1])%mod;
    sum2[now]=(sum2[now<<1]+sum2[now<<1|1])%mod;
}
inline void pushdown(int now,int l,int r)
{
    if (!tag[now]) return;
    tag[now<<1]=(tag[now<<1]+tag[now])%mod; tag[now<<1|1]=(tag[now<<1|1]+tag[now])%mod;
    sum2[now<<1]=(sum2[now<<1]+1ll*tag[now]*tag[now]*l+2ll*tag[now]*sum1[now<<1])%mod;
    sum2[now<<1|1]=(sum2[now<<1|1]+1ll*tag[now]*tag[now]*r+2ll*tag[now]*sum1[now<<1|1])%mod;
    sum1[now<<1]=(sum1[now<<1]+1ll*tag[now]*l)%mod; sum1[now<<1|1]=(sum1[now<<1|1]+1ll*tag[now]*r)%mod;
    tag[now]=0;
}
void build(int l,int r,int now)
{
    if (l==r)
    {
        sum1[now]=1ll*w[a[l]]%mod;
        sum2[now]=1ll*w[a[l]]*w[a[l]]%mod;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,now<<1);
    build(mid+1,r,now<<1|1);
    pushup(now);
}
void inchange(int L,int R,int l,int r,int now,int c)
{
    if (l>R||r<L) return;
    if (l>=L&&r<=R)
    {
        sum2[now]=(sum2[now]+1ll*c*c*(r-l+1)+2ll*c*sum1[now])%mod;
        sum1[now]=(sum1[now]+1ll*c*(r-l+1))%mod; tag[now]=(tag[now]+c)%mod; return;
    }
    int mid=(l+r)>>1; pushdown(now,mid-l+1,r-mid);
    if (mid>=R) inchange(L,R,l,mid,now<<1,c);
    else if (mid<L) inchange(L,R,mid+1,r,now<<1|1,c);
    else
    {
        inchange(L,mid,l,mid,now<<1,c);
        inchange(mid+1,R,mid+1,r,now<<1|1,c);
    }
    pushup(now);
}
ll ingetsum1(int L,int R,int l,int r,int now)
{
    if (l>R||r<L) return 0;
    if (l>=L&&r<=R) return sum1[now]%mod;
    int mid=(l+r)>>1; pushdown(now,mid-l+1,r-mid);
    if (mid>=R) return ingetsum1(L,R,l,mid,now<<1);
    if (mid<L) return ingetsum1(L,R,mid+1,r,now<<1|1);
    return (ingetsum1(L,mid,l,mid,now<<1)+ingetsum1(mid+1,R,mid+1,r,now<<1|1))%mod;
}
ll ingetsum2(int L,int R,int l,int r,int now)
{
    if (l>R||r<L) return 0;
    if (l>=L&&r<=R) return sum2[now]%mod;
    int mid=(l+r)>>1; pushdown(now,mid-l+1,r-mid);
    if (mid>=R) return ingetsum2(L,R,l,mid,now<<1);
    if (mid<L) return ingetsum2(L,R,mid+1,r,now<<1|1);
    return (ingetsum2(L,mid,l,mid,now<<1)+ingetsum2(mid+1,R,mid+1,r,now<<1|1))%mod;
}
inline void treechange(int x,int y,int val)
{
    while (top[x]!=top[y])
    {
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        inchange(idx[top[x]],idx[x],1,n,1,val);
        x=fa[top[x]];
    }
    if (dep[x]>dep[y]) swap(x,y);
    inchange(idx[x],idx[y],1,n,1,val);
}
inline ll treesum1(int x,int y)
{
    ll ans=0;
    while (top[x]!=top[y])
    {
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        ans=(ans+ingetsum1(idx[top[x]],idx[x],1,n,1))%mod;
        x=fa[top[x]];
    }
    if (dep[x]>dep[y]) swap(x,y);
    ans=(ans+ingetsum1(idx[x],idx[y],1,n,1))%mod;
    return ans;
}
inline ll treesum2(int x,int y)
{
    ll ans=0;
    while (top[x]!=top[y])
    {
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        ans=(ans+ingetsum2(idx[top[x]],idx[x],1,n,1))%mod;
        x=fa[top[x]];
    }
    if (dep[x]>dep[y]) swap(x,y);
    ans=(ans+ingetsum2(idx[x],idx[y],1,n,1))%mod;
    return ans;
}
int main()
{
    n=read(),m=read();
    for (reg int i=1;i<=n;w[i++]=read());
    for (reg int i=1;i<n;i++)
    {
        int x=read(),y=read();
        add_edge(x,y); add_edge(y,x);
    }
    dfs(1,0,1); dfs(1,1); build(1,n,1);
    while (m--)
    {
        int opt=read(),x=read(),y=read();
        if (opt==1) inchange(idx[x],idx[x]+tot[x]-1,1,n,1,y);
        if (opt==2) treechange(x,y,read());
        if (opt==3)
        {
            ll sum11=treesum1(x,y),sum22=treesum2(x,y);
            ll ans=((sum11*sum11-sum22)%mod*inv2%mod+mod)%mod;
            printf("%lld\n",ans);
        }
    }
    return 0;
}