本文移植自个人的原博客（原文）

题目链接

题目描述

题解

题目大意为有$n$个点，$m$条带权链，每个点只能被链覆盖一次，问可行覆盖方案的最大权值和。

该题动态规划方程较容易设计，可以设$f_x$为以$x$为根的子树所能达到的最大权值和，如果没有链以该点为$LCA$，那么$f_x=\sum f_{son}$，否则$f_x= \sum f_{不在链中且父亲节点在链中的子节点}+w$,但是对于第二种情况如果直接暴力找子节点，显然时间复杂度为$O(nq)$，不在可接受范围之内。

我们可以利用该种子节点的性质来为每个节点赋值，使得$\sum f_{不在链中且父亲节点在链中的子节点}$=$w_{x−>y}$和，从而通过树链剖分来实现$O(logn)$查询。考虑对于每一个已经求出的$f_x$，不妨将$w_{fa_x}+=f_x$，$w_x−=f_x$即可满足条件，理由如下：

对于父亲和自己均在链中的节点，则其贡献被计算了两次，一次为正，一次为负，即为没有贡献。
对于父亲和自己均不在链中的节点，则其没有贡献。
对于父亲在链中而自己不在链中的节点，其贡献只被计算了一次正值。
对于自己的链中而父亲不在链中的节点，显然只有当前节点（即询问节点的LCA），其$w$尚没有赋值。

#include<bits/stdc++.h>
#define lb(x) x&(-x)
using namespace std;
typedef long long ll;
const int N = 1e6+1;

int n,m,fa[N],st[N],ed[N],top[N],d[N],sz[N],son[N],totw;
int a[N],f[N],g[N],X[N],Y[N],W[N];

struct nd
{
    int ne[N*2],to[N*2];
    int head[N],cnt;
    void in(int x,int y){to[++cnt]=y;ne[cnt]=head[x];head[x]=cnt;}
    void init(){memset(head,0,sizeof(head));cnt=0;}
}e,e1;

void dfs1(int x)
{
    sz[x]=1;
    for(int i=e.head[x];i;i=e.ne[i])
    {
        int y=e.to[i];
        d[y]=d[x]+1;
        dfs1(y);

        sz[x]+=sz[y];
        if(sz[son[x]]<sz[y])son[x]=y;
    }
}

void dfs2(int x)
{
    st[x]=++totw;
    int y=son[x];if(!y)return;
    top[y]=top[x];dfs2(y);
    for(int i=e.head[x];i;i=e.ne[i])
    {
        y=e.to[i];
        if(y==son[x])continue;
        top[y]=y;
        dfs2(y);
    }
    ed[x]=totw;
}

void insert(int x,int d)
{
    for(int i=x;i<=n;i+=lb(i))a[i]+=d;
}

int sum(int x,int y)
{
    if(!x||!y)return 0;
    int ret=0;
    for(int i=y;i;i-=lb(i))ret+=a[i];
    for(int i=x-1;i;i-=lb(i))ret-=a[i];
    return ret;
}

int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(d[top[x]]<d[top[y]])swap(x,y);
        x=fa[top[x]];    
    }
    if(d[x]<d[y])return x;
    return y;
}

int query(int x,int y)
{
    int ret=0;
    while(top[x]!=top[y])
    {
        if(d[top[x]]<d[top[y]])swap(x,y);
        ret+=sum(st[top[x]],st[x]);
        x=fa[top[x]];
    }
    if(st[x]>st[y])swap(x,y);
    ret+=sum(st[x],st[y]);
    return ret;
}

int dp(int x)
{
    for(int i=e.head[x];i;i=e.ne[i])
    dp(e.to[i]),g[x]+=f[e.to[i]];
    f[x]=g[x];
    for(int i=e1.head[x];i;i=e1.ne[i])
    {
        int to=e1.to[i];
        f[x]=max(f[x],query(X[to],Y[to])+W[to]);
    }
    insert(st[x],-f[x]);
    if(fa[x])insert(st[fa[x]],f[x]);
}

int main()
{
//     freopen("c.in","r",stdin);
//    freopen("c.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n;++i)scanf("%d",&fa[i]),e.in(fa[i],i);
    top[1]=1;dfs1(1);dfs2(1);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&X[i],&Y[i],&W[i]);
        e1.in(lca(X[i],Y[i]),i);
    }
    dp(1);
    cout<<f[1];
}

Codeforces856D Masha and Cactus

题目链接

题目描述

题解