description

analysis

比较麻烦树形\(DP\)
不过这个我还是不算很懂……
下次要注意思考，不要怕麻烦
code

#pragma GCC optimize("O3")

#pragma G++ optimize("O3")

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<queue>

#define MAXN 300005

#define MAXM MAXN*2

#define INF 100000000000007

#define ll long long

#define fo(i,a,b) for (ll i=a;i<=b;++i)

#define fd(i,a,b) for (ll i=a;i>=b;--i)

#define rep(i,a) for (ll i=last[a];i;i=next[i])

using namespace std;

ll last[MAXM],next[MAXM],tov[MAXM],len[MAXM];

ll fa[MAXN],color[MAXN],f[MAXN],g[MAXN],h[MAXN],size[MAXN];

bool bz[MAXN];

ll n,T,tot,pos;

deque<ll>q;

inline ll read()

{

	ll x=0,f=1;char ch=getchar();

	while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}

	while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();

	return x*f;

}

inline void link(ll x,ll y,ll z){next[++tot]=last[x],last[x]=tot,tov[tot]=y,len[tot]=z;}

int main()

{

	freopen("T1.in","r",stdin);

	T=read();

	while (T--)

	{

		memset(f,0,sizeof(f));

		memset(g,0,sizeof(g));

		memset(h,0,sizeof(h));

		memset(bz,1,sizeof(bz));

		memset(fa,0,sizeof(fa));

		memset(size,0,sizeof(size));

		memset(last,0,sizeof(last));

		memset(next,0,sizeof(next));

		memset(tov,0,sizeof(tov));

		memset(len,0,sizeof(len));

		tot=pos=0,n=read();

		fo(i,1,n)color[i]=read();

		fo(i,1,n-1)

		{

			ll x=read(),y=read(),z=read();

			link(x,y,z),link(y,x,z);

		}

		q.push_back(1),bz[1]=0;

		while (q.size()<n)

		{

			ll x=q[pos++];

			rep(i,x)if (bz[tov[i]])++size[x],fa[tov[i]]=x,bz[tov[i]]=0,q.push_back(tov[i]);

		}

		while (q.size())

		{

			ll x=q[q.size()-1];q.pop_back();

			if (color[x])//白灰

			{

				f[x]=0;

				rep(i,x)if (fa[tov[i]]==x)

				{

					ll tmp=min(g[tov[i]],h[tov[i]])+len[i];

					f[x]+=min(f[tov[i]],tmp);

				}

			}

			else f[x]=INF;

			if (color[x]^1)//黑灰

			{

				g[x]=0;

				rep(i,x)if (fa[tov[i]]==x)

				{

					ll tmp=min(f[tov[i]],h[tov[i]])+len[i];

					g[x]+=min(g[tov[i]],tmp);

				}

				h[x]=INF;

				rep(i,x)if (fa[tov[i]]==x)

				{

					ll tmp=min(f[tov[i]],h[tov[i]])+len[i];

					tmp=h[tov[i]]+g[x]-min(g[tov[i]],tmp);

					h[x]=min(h[x],tmp);

				}

			}

			else//白

			{

				g[x]=INF,h[x]=0;

				rep(i,x)if (fa[tov[i]]==x)

				{

					ll tmp=min(f[tov[i]],h[tov[i]])+len[i];

					h[x]+=min(g[tov[i]],tmp);

				}

			}

		}

		printf("%lld\n",min(f[1],min(g[1],h[1])));

	}

	return 0;

}
巴特西

【JZOJ3347】树的难题

description

analysis

code

最新文章

热门文章
