P2700 逐个击破90分救不了(树形DP做法)
查看原帖
P2700 逐个击破90分救不了(树形DP做法)
180924
FLAT_LCH楼主2021/12/25 17:19
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct bian
{
	int v,nex,c;
}side[500000];
struct node
{
	int fa,dp[2],head;
	bool o,vis;
}p[500000];

int n,m,len=0;

inline int rd()
{
	int s=0;char x='x';
	while(x<'0'||x>'9')x=getchar();
	while(x>='0'&&x<='9'){s=s*10+(x^48);x=getchar();}
	return s;
}

inline void lian(int u,int v,int c)
{
	len++;side[len].v=v;side[len].c=c;side[len].nex=p[u].head;p[u].head=len;
	len++;side[len].v=u;side[len].c=c;side[len].nex=p[v].head;p[v].head=len;
}

inline void readd()
{
	int u,v,c;
	n=rd();m=rd();
	
	for(int i=1;i<=m;i++)
	{
		u=rd()+1;
		p[u].o=true;
	}
	
	for(int i=1;i<n;i++)
	{
		u=rd()+1;v=rd()+1;c=rd();
		lian(u,v,c);
	}
}

void dp(int u)
{
	if(p[u].o){p[u].dp[0]=0x3f3f3f3f;p[u].dp[1]=0;}
	else{p[u].dp[0]=0;p[u].dp[1]=0;}
	int v,c,maxx=0;
	p[u].vis=true;
	for(int i=p[u].head;i;i=side[i].nex)
	{
		v=side[i].v;c=side[i].c;
		if(!p[v].vis)
		{
			dp(v);
			if(p[u].o)p[u].dp[1]+=min(p[v].dp[0],p[v].dp[1]+c);
			else
			{
				p[u].dp[0]+=min(p[v].dp[0],p[v].dp[1]+c);
				if(p[v].dp[0]<=p[v].dp[1]+c)
				{
					p[u].dp[1]+=p[v].dp[0];
					maxx=max(maxx,p[v].dp[0]-p[v].dp[1]);
				}
				else 
				{
					p[u].dp[1]+=p[v].dp[1]+c;
					maxx=max(maxx,c);
				}
			}
		}
	}
	if(!p[u].o)p[u].dp[1]-=maxx;
}

int main()
{
	readd();
	dp(3);
	cout<<min(p[3].dp[0],p[3].dp[1]);
	return 0;
}
2021/12/25 17:19
加载中...