暴力

首先观察询问，树上链$u\to v$点权加，显然可以用树上差分LOJ dfs序4 $O(1)$完成此操作，然后考虑对这些权值对答案的影响？
设经过某点$u$符合条件的路径条数为$\text{path}_u$
当$u$点权$+c$后，那么它对答案的贡献则是$\text{path}_u×c$，而对于$u\to v$这条路径来说，点权全部$+c$后对答案的贡献是

$$\sum_{i \in u\to v} \text{path}_i×c$$

如果完成$\text{path}_u$预处理后以及最开始的答案，之后每个操作对答案的贡献可根据上述方法求出。

观察题目数据范围发现前$50\text{pts}$的$n\leq 2000$，这就很容易了，暴力枚举每个点为起点，把所有路径都拿出来然后记录一下每条路径，当一条路径符号题意时维护$\text{path}_u$即可。

然后观察到$60\text{pts}$的点是一条链，可以乱搞一下在骗$10\text{pts}$

#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
using ll=long long;
constexpr int N=2010;
constexpr ll mod=1e9+7;
int h[N],e[2*N],ne[2*N],idx;
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
int n,m,L,R;
int a[N],d[N];
bool vis[N];
ll b[N],ans,path[N];
int pre[N];
void bfs(int S)
{
    memset(d,0,sizeof(int)*(n+1));
    memset(pre,0,sizeof(int)*(n+1));
    memset(b,0,sizeof(ll)*(n+1));
    memset(vis,0,sizeof(bool)*(n+1));
    queue<int> q;
    q.push(S); d[S]=0;b[S]=a[S];
    vis[S]=1;
    while(q.size())
    {
        int u=q.front();q.pop();
        for(int i=h[u];i!=-1;i=ne[i])
        {
            int v=e[i];
            if(!vis[v])
            {
                d[v]=d[u]+1;
                b[v]=(b[u]+a[v])%mod;
                pre[v]=u;//记录路径
                q.push(v);
                vis[v]=1;
            }
        }
    }
    for(int i=1;i<=n;i++)
        if(L<=d[i]&&d[i]<=R) 
        {
            ans=(ans+b[i])%mod;
            int u=i;
            while(u) //维护路径path
            {
                path[u]++;
                u=pre[u];
            }
        }
}
int sz[N],fa[N],dep[N],son[N];
ll s[N];
void dfs1(int u)
{
    dep[u]=dep[fa[u]]+1;
    sz[u]=1;
    s[u]=path[u]+s[fa[u]];// 预处理s数组
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(v==fa[u]) continue;
        fa[v]=u;
        dfs1(v);
        sz[u]+=sz[v];
        if(sz[son[u]]<sz[v]) son[u]=v;
    }
}
int dfn[N],timestamp,top[N];
void dfs2(int u,int t)
{
    dfn[u]=++timestamp;
    top[u]=t;
    if(son[u]) dfs2(son[u],t);
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
int lca(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]>=dep[top[v]]) 
            u=fa[top[u]];
        else 
            v=fa[top[v]];
    }
    return dep[u]>=dep[v]?v:u;
}
void init(int n)
{
    memset(h,-1,sizeof(int)*(n+1));
    memset(s,0,sizeof(ll)*(n+1));
    memset(path,0,sizeof(ll)*(n+1));
    memset(dfn,0,sizeof(int)*(n+1));
    memset(son,0,sizeof(int)*(n+1));
    memset(top,0,sizeof(int)*(n+1));
    memset(sz,0,sizeof(int)*(n+1));
    timestamp=idx=0;ans=0;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>m>>L>>R;
        init(n);
        --L,--R;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=2;i<=n;i++)
        {
            int p;
            cin>>p;
            add(i,p),add(p,i);
        }
        for(int i=1;i<=n;i++) bfs(i);
        ans=1ll*ans*500000004%mod;
        for(int i=1;i<=n;i++) path[i]/=2;
        dfs1(1);
        dfs2(1,1);
        while(m--)
        {
            int a,b,c;
            cin>>a>>b>>c;
            int anc=lca(a,b);
            ans=(ans+(s[a]+s[b]-s[anc]-s[fa[anc]])*c%mod)%mod;
            cout<<ans<<'\n';
        }
    }
}

点分治

学过点分治的一看就知道是个点分治的题，但是看到之后就懒得写~代码又臭又长

考虑如何通过点分治求出最初的答案以及维护出数组$\text{path}_u$？

首先对于最初的答案显然就是个点分治模板题这里不在赘述，而对于$\text{path}_u$显然不能像暴力一下记录路径然后加，这样就没必要分治了~~

点分治的技巧是花费log的代价把任意路径变成通过当前根节点的路径，也就是目前考虑的路径都会穿过当前根节点

既然穿过根节点，我们只需要在每条路径的端点记录一下，显然如果当前点是一个路径的端点，那么它的祖先节点也需要被这条路径覆盖，只需要一遍dfs把子节点“回收”一下就能够实现将此路径覆盖的点都标记。

不过一条路径是有两个端点的，但是点分治的过程（枚举当前子树的端点，在前面的子树中查找符合条件的另一个端点）只能知道当前的一个端点，而另一个端点我们是不知道的。

比如当前子树$v$的一个端点$b$，而前面的子树有一个端点$a$，也就是$a\to rt\to b$这条路径符合条件，点分治的过程中我们只知道当前子树$v$的端点$b$

这里我采用先从前向后遍历子树（找到端点$b$），然后再从后往前遍历子树（找到端点$a$），不难发现这样枚举都会枚举到$a\to rt\to b$这条路径，并且一次是端点$b$，另一次是端点$a$（注意rt可能会多算需要减去）

对于直接到当前根节点的路径我们特殊处理即可

时间复杂度$O(\alpha n\log^2 n+m\log n)$

#pragma GCC optimize(2)
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
using ll=long long;
constexpr int N=100010;
constexpr ll mod=1e9+7;
int h[N],h2[N],e[4*N],ne[4*N],idx;
void add(int h[],int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
int n,m,L,R;
int a[N],p[N];
int sz[N],fa[N],dep[N],son[N];
int dfn[N],timestamp,top[N];
ll s[N];
ll path[N],ans;
int rt;
ll fw[2][N];
int lowbit(int x){return x&-x;}
void update(int i,int k,ll x){if(k<=0) return;for(;k<=n;k+=lowbit(k)) fw[i][k]=(fw[i][k]+x)%mod;}
ll query(int i,int k){if(k<=0) return 0;ll res=0;for(;k;k-=lowbit(k)) res=(res+fw[i][k])%mod;return res;}
struct node
{
    int d,u;
    ll w;
}d[N];
ll b[N];int cnt;
bool del[N];
void dfs_rt(int u,int fa,int tot)//找重心
{
    sz[u]=1;
    int mx=0;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(v==fa||del[v]) continue;
        dfs_rt(v,u,tot);
        sz[u]+=sz[v];
        mx=max(mx,sz[v]);
    }
    mx=max(mx,tot-sz[u]);
    if(2*mx<=tot) rt=u;
}
void dfs_sz(int u,int fa)//处理sz
{
    sz[u]=1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(v==fa||del[v]) continue;
        dfs_sz(v,u);
        sz[u]+=sz[v];
    }
}
void dfs_dist(int u,int fa,int dist,ll w)//找路径
{
    w%=mod;
    d[++cnt]={dist,u,w};
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(v==fa||del[v]) continue;
        dfs_dist(v,u,dist+1,w+a[v]);
    }
}
void dfs_fw(int u,int fa,int dist,ll w)//清空树状数组
{
    w%=mod;
    update(0,dist,-w);
    update(1,dist,-1);
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(v==fa||del[v]) continue;
        dfs_fw(v,u,dist+1,w+a[v]);
    }
}
void dfs_add(int u,int fa)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(v==fa||del[v]) continue;
        dfs_add(v,u);
        b[u]+=b[v];b[u]%=mod;
    }
    path[u]+=b[u];path[u]%=mod;
}
void dfs_b(int u,int fa)//清空b数组
{
    b[u]=0;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(v==fa||del[v]) continue;
        dfs_b(v,u);
    }
}
void dfs_calc(int u,int fa,int dist,ll w)//到当前根节点特殊路径
{
    w%=mod;
    if(L<=dist&&dist<=R) b[u]++,ans=(ans+w)%mod;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(v==fa||del[v]) continue;
        dfs_calc(v,u,dist+1,w+a[v]);
    }
}
void work(int u,int tot)
{
    dfs_rt(u,0,tot);
    u=rt;
    dfs_sz(u,0);
    del[u]=1;
    //顺着子树
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(del[v]) continue;
        cnt=0;// 指针
        dfs_dist(v,u,1,a[v]);
        for(int k=1;k<=cnt;k++) ans=(ans+query(0,R-d[k].d)-query(0,L-1-d[k].d))%mod;
        for(int k=1;k<=cnt;k++) 
        {
            int tmp=query(1,R-d[k].d)-query(1,L-1-d[k].d);
            ans=(ans+1ll*d[k].w%mod*tmp%mod)%mod;
            b[u]-=tmp;//防止当前根节点重复算
            b[d[k].u]+=tmp;
        }
        for(int k=1;k<=cnt;k++)
            update(0,d[k].d,d[k].w+a[u]),update(1,d[k].d,1);
    }
    dfs_fw(u,0,0,a[u]);
    //逆子树
    for(int i=h2[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(del[v]) continue;
        cnt=0;// 指针
        dfs_dist(v,u,1,a[v]);
        for(int k=1;k<=cnt;k++) 
        {
            int tmp=query(1,R-d[k].d)-query(1,L-1-d[k].d);
            b[d[k].u]+=tmp;
        }
        for(int k=1;k<=cnt;k++)
            update(0,d[k].d,d[k].w+a[u]),update(1,d[k].d,1);
    }
    dfs_calc(u,0,0,a[u]);
    dfs_add(u,0);
    dfs_fw(u,0,0,a[u]); 
    dfs_b(u,0);

    for(int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(del[v]) continue;
        work(v,sz[v]);
    }

}
//==================================================点分治
void dfs1(int u)
{
    dep[u]=dep[fa[u]]+1;
    sz[u]=1;
    s[u]=(path[u]+s[fa[u]])%mod;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(v==fa[u]) continue;
        fa[v]=u;
        dfs1(v);
        sz[u]+=sz[v];
        if(sz[son[u]]<sz[v]) son[u]=v;
    }
}
void dfs2(int u,int t)
{
    dfn[u]=++timestamp;
    top[u]=t;
    if(son[u]) dfs2(son[u],t);
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
int lca(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]>=dep[top[v]]) 
            u=fa[top[u]];
        else 
            v=fa[top[v]];
    }
    return dep[u]>=dep[v]?v:u;
}
//================================================== 树剖求lca
void init(int n)
{
    memset(h,-1,sizeof(int)*(n+1));
    memset(h2,-1,sizeof(int)*(n+1));
    memset(path,0,sizeof(ll)*(n+1));
    memset(s,0,sizeof(ll)*(n+1));
    memset(dfn,0,sizeof(int)*(n+1));
    memset(son,0,sizeof(int)*(n+1));
    memset(top,0,sizeof(int)*(n+1));
    memset(sz,0,sizeof(int)*(n+1));
    memset(del,0,sizeof(bool)*(n+1));
    timestamp=idx=0;ans=0;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d%d",&n,&m,&L,&R);
        init(n);
        --L,--R;
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        for(int i=2;i<=n;i++) scanf("%lld",&p[i]);
        for(int i=2;i<=n;i++) add(h,i,p[i]),add(h,p[i],i);//顺着子树
        for(int i=n;i>=2;i--) add(h2,i,p[i]),add(h2,p[i],i);//逆着子树

        work(1,n);
        dfs1(1);
        dfs2(1,1);

        while(m--)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            int anc=lca(a,b);
            ans=(ans+(s[a]+s[b]-s[anc]-s[fa[anc]])*c%mod)%mod;
            ans=(ans+mod)%mod;
            printf("%lld\n",ans);
        }
    }
}

这题真蛋疼，写完还因为常数太大（点分治9次dfs）TLE了，吸氧才AC
也没看懂闫神的代码，闫神的代码为啥常数能那么小呢~~