自动搬运

查看原文

来自洛谷，原作者为

	takanashi_mifuru 一往无前，披星戴月，勿要回首 | 会いたい愛が痛いアイロニー | 时在今日，天下当倾 | 「私が毒を毒づくのは 毒が好きだったってわけさ」

搬运于2025-08-24 22:37:41，当前版本为作者最后更新于2022-11-23 11:29:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

我从来不使用 STL，使用 STL 让我感到不舒服，我不会再使用 STL 写题，望周知。

为什么题解区官方题解都没有啊，不是很能理解。

关注莲莲，好运连连！

思路

Subtask 1

一种烟花只会指向另一种烟花，非常像基环树。

$m=0$，我们考虑基环树上动态规划。

我们考虑先在子树上动态规划，然后再把答案丢到环上统计起来。

设 $dp_{i,0/1}$ 表示 在以 $i$ 为根的子树中，第 $i$ 个点取还是不取得到的最大点权。

转移方程非常明显，$dp_{i,0}=dp_{i,0}+\max\left(dp_{v,0},dp_{v,1}\right)$，$dp_{i,1}=dp_{i,0}+\max\left(dp_{v,0},dp_{v,1}-w\right)$，其中 $v$ 为 $i$ 的子结点，$w$ 为 $i$ 到 $v$ 的这条边的边权。

你可能会想，拉到环上像树一样动态规划就能解决这个难题，可事实并非如此，起点会说：你真以为终点只由终点的前驱更新啊？你爹都不认识了是吧？

在环上合并这些信息，你应该做过 P2607，像这个题一样，钦点环上的一个起点的状态，一个环就会被破成一条链，在这条链上动态规划，而如果起点的状态为选，终点的状态也为选，就需要额外减掉起点与终点的边权，在合计 $4$ 种情况中取出最大值即可。

虽然这种做法只能在及其罕见的情况下起到作用，但是可以拿到 $30$ 分。

Subtask 2

无特殊情况。

考虑到关系 $2$，即限制一些烟花必须一起燃放，考虑用并查集将他们合并，合并起来后用他们的关系建立新图，由于题目给出的限制，一个大点至多连出去一条边。

于是新的图就会是一个基环树与树的森林，在上面动态规划就能解决这个难题。

这个题是比较卡的，如果你使用了大量 STL，就会出现罕见的 TLE，但是没关系，开 O2 就能跑过，任何 STL 终将绳之以法。

如果你因为某些原因 RE 或者 WA 了，我给出一组 hack。

input:
10 2
7 4 65
40 1 74
48 8 32
77 5 94
74 3 79
65 8 19
38 5 80
60 4 48
60 3 1
15 9 25
1 3 1 7 6
4 3 4 9 2

output:
270

代码

#include<bits/stdc++.h>
#define mkpr make_pair
#define int long long
using namespace std;
const int MAXN=5e5+5;
int n,q;
class UFS{
    public:
    int father[MAXN];
    void init(){
        for(int i=1;i<=n;i++)father[i]=i;
        return;
    }
    int find(int x){
        if(father[x]==x)return x;
        return father[x]=find(father[x]);
    }
    void unionn(int x,int y){
        x=find(x),y=find(y);
        if(x^y)father[x]=y;
        return;
    }
}P;
int cnt=1;
struct edge{
    int v,w;
    int nxt;
}E[MAXN<<1];
int head[MAXN];
struct node{
    int v,a,b;
}Fir[MAXN];
struct point{
    int v,w;
};
int D[MAXN];
int C[MAXN];
bool vis[MAXN];
int R[MAXN];
bool tag[MAXN];
bool bj[MAXN];
vector<point> ljb[MAXN];
int dp[MAXN][2];
int num[MAXN][2];
int id[MAXN];
void init(){
    scanf("%lld%lld",&n,&q);
    P.init();
    for(int i=1;i<=n;i++){
        int v,a,b;
        scanf("%lld%lld%lld",&v,&a,&b);
        Fir[i]=node{v,a,b};
    }
    for(int i=1;i<=q;i++){
        int p,k;
        scanf("%lld%lld",&p,&k);
        while(k--){
            int x;
            scanf("%lld",&x);
            P.father[x]=p;
        }
    }
    return;
}
void addedge(int u,int v,int w){
    cnt++;
    E[cnt].v=v;
    E[cnt].w=w;
    E[cnt].nxt=head[u];
    head[u]=cnt;
    return;
}
void getE(){
    map<pair<int,int>,bool> mp;
    for(int i=1;i<=n;i++){
        if(P.father[i]==i){
            int u=i;
            int v=P.find(Fir[i].a);
            if(u>v)swap(u,v);
            if(mp[mkpr(u,v)]){
                int tmp=i^u^v;
                C[i]=C[tmp]^1;
                continue;
            }
            if(u==v)continue;
            mp[mkpr(u,v)]=true;
            addedge(u,v,0);
            addedge(v,u,0);
            C[i]=cnt-1;
        }
    }
    for(int i=1;i<=n;i++){
        int v1=P.find(Fir[i].a);
        int v2=P.find(Fir[P.find(i)].a);
        if(v1==v2){
            int fx=P.find(i);
            int e=C[fx];
            E[e].w+=Fir[i].b;
            E[e^1].w+=Fir[i].b;
        }
    }
    return;
}
void getD(){
    for(int i=1;i<=n;i++){
        D[P.find(i)]+=Fir[i].v;
    }
    for(int i=1;i<=n;i++){
        int fx=P.find(i);
        int v=P.find(Fir[i].a);
        if(v==fx){
            D[fx]-=Fir[i].b;
        }
    }
    return;
}
void getnew(){
    vector<int> A;
    for(int i=1;i<=n;i++){
        if(P.find(i)==i)A.push_back(i);
    }
    for(int i=0;i<A.size();i++){
        id[A[i]]=i+1;
    }
    for(int i=0;i<A.size();i++){
        int tmp=A[i];
        D[id[tmp]]=D[tmp];
        for(int j=head[tmp];j;j=E[j].nxt){
            int v=E[j].v;
            int w=E[j].w;
            ljb[id[tmp]].push_back(point{id[v],w});
        }
    }
    n=A.size();
    return;
}
void getR(){
    for(int i=1;i<=n;i++){
        for(int j=0;j<ljb[i].size();j++){
            int v=ljb[i][j].v;
            R[v]++;
        }
    }
    return;
}
vector<point> cir;
bool pos[MAXN];
void find(int cur,int fa,int w){
    cir.push_back(point{cur,w});
    pos[cur]=true;
    for(int i=0;i<ljb[cur].size();i++){
        int v=ljb[cur][i].v;
        int w=ljb[cur][i].w;
        if(v==fa)continue;
        if(!pos[v]&&vis[v]){
            find(v,cur,w);
            break;
        }
        if(pos[v])cir[0].w+=w;
    }
    return;
}
void gettag(int cur){
    bj[cur]=true;
    tag[cur]=true;
    for(int i=0;i<ljb[cur].size();i++){
        int v=ljb[cur][i].v;
        if(!tag[v])gettag(v);
    }
    return;
}
void getcir(int S){
    for(int i=1;i<=n;i++)tag[i]=false;
    cir.clear();
    gettag(S);
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(R[i]==1&&tag[i])q.push(i);
        vis[i]=false;
    }
    while(!q.empty()){
        int t=q.front();
        vis[t]=true;
        q.pop();
        for(int i=0;i<ljb[t].size();i++){
            int v=ljb[t][i].v;
            R[v]--;
            if(vis[v])continue;
            if(R[v]==1)q.push(v);
        }
    }
    for(int i=1;i<=n;i++){
        vis[i]^=1;
    }
    for(int i=1;i<=n;i++){
        if(vis[i]&&tag[i]){
            find(i,0ll,0ll);
            break;
        }
    }
    return;
}
void getDP(int cur,int fa){
    dp[cur][0]=0;
    dp[cur][1]=D[cur];
    for(int i=0;i<ljb[cur].size();i++){
        int v=ljb[cur][i].v;
        int w=ljb[cur][i].w;
        if((v^fa)&&!vis[v]){
            getDP(v,cur);
            dp[cur][0]+=max(dp[v][0],dp[v][1]);
            dp[cur][1]+=max(dp[v][0],dp[v][1]-w);
        }
    }
    return;
}
void getG(){
    init();//读入
    getE();//建边
    getD();//建点
    getnew();//重置整张图
    getR();//统计度数方便拓扑
    return;
}
int getans(){
    int ans=0;
    for(int i=1;i<=n;i++){
        if(bj[i])continue;
        getcir(i);//找环，塞进cir数组里面
        int len=cir.size();
        if(len==0){//无环，树，直接跑树形dp
            getDP(i,0);
            ans+=max(dp[i][0],dp[i][1]);
            continue;
        }
        for(point S:cir){//处理挂在环上的子树
            getDP(S.v,0);
        }
        int sum1=0;
        int sum2=0;
        num[0][0]=dp[cir[0].v][0];//强制起点不取
        num[0][1]=-1e18;
        for(int i=1;i<cir.size();i++){
            num[i][0]=max(num[i-1][0],num[i-1][1])+dp[cir[i].v][0];
            num[i][1]=max(num[i-1][0],num[i-1][1]-cir[i].w)+dp[cir[i].v][1];
        }
        sum1=max(num[len-1][0],num[len-1][1]);
        num[0][1]=dp[cir[0].v][1];//强制起点取
        num[0][0]=-1e18;
        for(int i=1;i<len;i++){
            num[i][0]=max(num[i-1][0],num[i-1][1])+dp[cir[i].v][0];
            num[i][1]=max(num[i-1][0],num[i-1][1]-cir[i].w)+dp[cir[i].v][1];
        }
        sum2=max(num[len-1][0],num[len-1][1]-cir[0].w);
        ans+=max(sum1,sum2);
    }
    return ans;
}
int solve(){
    getG();//建立新图
    return getans();
}
signed main(){
    printf("%lld\n",solve());
    return 0;
}

我的写法比较愚蠢，要开 O2 才能过，这里仅作参考。