CF960E

· · 题解

题意

给出一颗有点权的树，树上有向路径 \{a_1,a_2,\cdots,a_k \} 的权值被定义为：

\sum_{i=1}^k(-1)^{i+1}\cdot w_{a_i}

求树上所有路径的权值和。

思路

拿来练习点分治真的很不错。

这个题是询问树上所有路径和，首先想到点分治，考虑如果快速求出来经过根节点的答案。

首先不难想到按顺序考虑子树，考虑一个的贡献后加一个（这个会点分治的应该都会吧）。

想如何维护这个贡献，不难想到对树上路径按照结尾节点深度的奇偶性分层，则答案就很好统计。

由于限制路径必须经过根节点，所以我们发现合法路径两个端点必须处在奇偶性相同的层上（根节点两侧的正负必须保持一致）。

于是只需要维护一下已经遍历过部分的奇数/偶数深度的路径权值和，数量和，记为 sum1,sum2,siz1,siz2。

则在算贡献的时候直接大力讨论取对应奇偶性的节点考虑即可，如果当前是奇数，则算上贡献 sum1+siz1\times dis，偶数就注意了，我们的 dis 是按照根节点是正数的情况求的，此时开头节点的权值是负的，不合法，所以路径贡献整体乘上 -1 即可。

实现细节看代码。

然后就可以快乐分治下去了。

code

这里有一个坑点，求重心要重新求 siz，虽然不求复杂度正确，但是有一个较大的常数，这里在处理当前节点的时候顺手重新求一遍 siz 即可，否则会 TLE 72。

const int MAXN=2e5+10;
vector<int>e[MAXN];
int siz[MAXN],son[MAXN];
bool book[MAXN];
int rt,sum;
void getroot(int u,int fa)
{
    siz[u]=1,son[u]=0;
    for(auto&v:e[u])if(v^fa&&!book[v])
    {
        getroot(v,u);
        siz[u]+=siz[v];
        cmax(son[u],siz[v]);
    }
    cmax(son[u],sum-siz[u]);
    if(son[u]<son[rt])rt=u;

}
int a[MAXN];
ll ans=0;
ll s1=0,s2=0;
int siz1,siz2;
void getdis(int u,int fa,int op,int d)
{
    if(op)(d+=a[u])%=mod,ans+=(s1+(ll)d*siz1)%mod;
    else (d+=mod-a[u])%=mod,ans+=mod-(s2+(ll)d*siz2)%mod;
    for(auto& v:e[u])
    {
        if(v==fa||book[v])continue;
        getdis(v,u,op^1,d); 
    }   
}
void insert(int u,int fa,int op,int d)
{
    if(op)(d+=a[u])%=mod,siz1++,(s1+=d)%=mod;
    else (d+=mod-a[u])%=mod,siz2++,(s2+=d)%=mod;
    siz[u]=1;
    for(auto& v:e[u])
    {
        if(v==fa||book[v])continue;
        insert(v,u,op^1,d); 
        siz[u]+=siz[v];
    }
}
void getans(int u)
{
    s1=0,s2=0;
    siz1=siz2=0;
    s1+=a[u],siz1++;
    for(auto& v:e[u])if(!book[v])
    {   
        getdis(v,u,0,0);
        insert(v,u,0,a[u]);//这里带上根节点的权值，原因显然
        siz[u]+=siz[v];//在这里顺手求一下当前树正确的 siz
    }
}
void dfs(int u)
{
    book[u]=1;
    getans(u);
    for(auto&v:e[u])if(!book[v])
    {
        rt=0,sum=siz[v],getroot(v,u);   
        dfs(rt);
    }
}
signed main()
{
    son[0]=1e9;
    int n=R();
    for(int i=1;i<=n;i++)a[i]=(R()%mod+mod)%mod;
    int u,v;
    for(int i=1;i<n;i++)
    {
        u=R(),v=R();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    sum=n;

    dfs(1);
    ans=ans*2%mod;//有向，所以乘 2
    for(int i=1;i<=n;i++)ans+=a[i];//一个点也算路径！
    cout<<ans%mod;
    return 0;
}