题面

CJY很喜欢吃奶酪，于是YJC弄到了一些奶酪，现在YJC决定和CJY分享奶酪。

YJC弄到了n-1块奶酪，于是他把奶酪挂在了一棵n个结点的树上，每根树枝上挂一块奶酪，每块奶酪都有重量。

YJC和CJY决定这样分奶酪：首先砍掉一根树枝，把树分成两部分，每人取一部分，然后各自在自己取的那部分树上选择一条路径并取走路径上的奶酪，然后把剩下的奶酪拿去喂老鼠。

两人都想让自己取走总重量尽量大的奶酪，但他们不知道砍掉哪一根树枝最好。所以他们想让你计算，对于每一根树枝，砍掉之后每个人取走的奶酪的总重量的最大值。

对于100%的数据，保证n<=4*10^6,w<=106

100

可以利用树形dp直接做。

维护：

1.一个点往下的最长链\(f_i\)；

2.一个点往下的次长链\(g_i\)；

3.一个点往下的次次长链\(h_i\)；

4.一个子树内的最长链\(mx_i\)；

5.一个点的所有儿子\(mx\)的最大值\(mxx_i\)；

6.一个点的所有儿子\(mx\)的次大值\(mxxx_i\)；

7.一个点往上走的最长链\(F_i\)；

8.不包含一个点及其子树的最长链\(Mx_i\)

最后答案就是\(mx\)和\(Mx\)。

时间复杂度为\(O(n)\)。

为什么可以用树形dp

树静态。

Code

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#define ll long long

#define fo(i,x,y) for(ll i=x;i<=y;i++)

#define fd(i,x,y) for(ll i=x;i>=y;i--)

using namespace std;

const char* fin="cheese.in";

const char* fout="cheese.out";

const ll inf=0x7fffffff;

const ll maxn=4000007,maxm=maxn*2;

const ll mo=2333333333333333;

ll n,bz[maxn],id,fi[maxn],la[maxm],ne[maxm],va[maxm],tot=1,tmb,ban;

ll f[maxn],g[maxn],h[maxn],mx[maxn],mxx[maxn],mxxx[maxn],fa[maxn],F[maxn],Mx[maxn];

ll ans,ans1,ans2;

void add_line(ll a,ll b,ll c){

	tot++;

	ne[tot]=fi[a];

	la[tot]=b;

	va[tot]=c;

	fi[a]=tot;

}

void dfs(ll v,ll from){

	for(ll k=fi[v];k;k=ne[k])

		if (la[k]!=from){

			fa[la[k]]=v;

			dfs(la[k],v);

			mx[v]=max(mx[la[k]],mx[v]);

			ll tmp=f[la[k]]+va[k];

			if (tmp>=f[v]){

				h[v]=g[v];

				g[v]=f[v];

				f[v]=tmp;

			}else if (tmp>=g[v]){

				h[v]=g[v];

				g[v]=tmp;

			}else if (tmp>=h[v]) h[v]=tmp;

			if (mx[la[k]]>=mxx[v]){

				mxxx[v]=mxx[v];

				mxx[v]=mx[la[k]];

			}else if (mx[la[k]]>=mxxx[v]) mxxx[v]=mx[la[k]];

		}

	mx[v]=max(mx[v],f[v]+g[v]);

}

void Dfs(ll v,ll from){

	for(ll k=fi[v];k;k=ne[k])

		if (la[k]!=from){

			Mx[la[k]]=Mx[v];

			if (mx[la[k]]==mxx[v]) Mx[la[k]]=max(Mx[la[k]],mxxx[v]);

			else Mx[la[k]]=max(Mx[la[k]],mxx[v]);

			if (f[v]==f[la[k]]+va[k]){

				F[la[k]]=max(F[v]+va[k],g[v]+va[k]);

				Mx[la[k]]=max(Mx[la[k]],g[v]+max(h[v],F[v]));

			}else{

				F[la[k]]=max(F[v]+va[k],f[v]+va[k]);

				if (g[v]==f[la[k]]+va[k]) Mx[la[k]]=max(Mx[la[k]],f[v]+max(h[v],F[v]));

				else Mx[la[k]]=max(Mx[la[k]],f[v]+max(g[v],F[v]));

			}

			Dfs(la[k],v);

		}

}

ll read(){

	ll x=0;

	char ch=getchar();

	while (ch<'0' || ch>'9') ch=getchar();

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

	return x;

}

int main(){

	freopen(fin,"r",stdin);

	freopen(fout,"w",stdout);

	n=read();

	fo(i,1,n-1){

		ll j=read();

		ll k=read();

		ll l=read();

		add_line(j,k,l);

		add_line(k,j,l);

	}

	dfs(1,0);

	Dfs(1,0);

	fo(i,1,n-1){

		ll u=la[i*2+1],v=la[i*2];

		if (fa[v]==u) swap(u,v);

		ans1=mx[u];

		ans2=Mx[u];

		ans=(ans+max(ans1,ans2)*23333+min(ans2,ans1)*2333+233*i*i+23*i+2)%mo;

		//printf("%lld %lld\n",ans1,ans2);

	}

	cout<<ans<<endl;

	return 0;

}

巴特西

【JZOJ5071】【GDSOI2017第二轮模拟】奶酪树形dp

题面

100

为什么可以用树形dp

Code

最新文章

热门文章

巴特西

【JZOJ5071】【GDSOI2017第二轮模拟】奶酪 树形dp

题面

100

为什么可以用树形dp

Code

最新文章

热门文章

【JZOJ5071】【GDSOI2017第二轮模拟】奶酪树形dp