説明
takanashi_mifuru
·
·
题解
前言
我从来不使用 STL，使用 STL 让我感到不舒服，我不会再使用 STL 写题，望周知。
为什么题解区官方题解都没有啊，不是很能理解。
关注莲莲，好运连连！
思路
Subtask 1
一种烟花只会指向另一种烟花，非常像基环树。
我们考虑先在子树上动态规划，然后再把答案丢到环上统计起来。
设 $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
```
### 代码
```cpp
#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 才能过，这里仅作参考。