正题

题目链接:https://www.luogu.com.cn/problem/P4201

题目大意

给出\(n\)个点的一棵树开始所有边都是白色，选出若干条没有公共点的路径将上面所有边变为黑色。

要求所有点到\(1\)号点的路径上经过的白色边的数量的最大值最小。

求最小值和方案数

解题思路

直接记录最小值的树形\(dp\)可以计算出第一个答案，但是第二个答案就有点麻烦了，因为有的不取最小值也不一定影响答案。

而可以发现如果按照树链剖分的思路来做答案是不会超过\(\log_2n\)的，进一步证明的话其实可以得到答案不会超过\(\log_3 n\)的结论，因为一个顶部节点实际上是可以延伸出\(2\)条路径的。

这样就可以直接\(dp\)了，设\(f_{i,j,0/1/2}\)表示到节点\(i\)，最大值为\(j\)，节点\(i\)已经往子树中延伸了\(0/1/2\)条路径时的方案数。

那么转移起来就很方便了，需要注意答案可能是模数的倍数，所以我们需要另开一个变量来记录每种情况是否有可能。

时间复杂度\(O(n\log_3 n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const ll N=1e5+10;

struct node{

	ll to,next;

}a[N<<1];

ll n,m,P,tot,ls[N],f[N][12][3];

bool v[N][12][3];

void addl(ll x,ll y){

	a[++tot].to=y;

	a[tot].next=ls[x];

	ls[x]=tot;return;

}

void dp(ll x,ll fa){

	for(ll i=1;i<=11;i++)f[x][i][0]=v[x][i][0]=1;

	for(ll i=ls[x];i;i=a[i].next){

		ll y=a[i].to;

		if(y==fa)continue;dp(y,x);

		for(ll j=1;j<=11;j++){

			ll cho=(f[y][j-1][0]+f[y][j-1][1]+f[y][j-1][2])%P;

			ll che=(f[y][j][0]+f[y][j][1])%P;

			ll chv=v[y][j-1][0]|v[y][j-1][1]|v[y][j-1][2];

			ll chn=v[y][j][0]|v[y][j][1];

			(f[x][j][2]=f[x][j][1]*che+f[x][j][2]*cho)%=P;

			(f[x][j][1]=f[x][j][0]*che+f[x][j][1]*cho)%=P;

			(f[x][j][0]*=cho)%=P;

			v[x][j][2]=v[x][j][1]&chn|v[x][j][2]&chv;

			v[x][j][1]=v[x][j][0]&chn|v[x][j][0]&chv;

			v[x][j][0]&=chv;

		}

	}

	return;

}

signed main()

{

	scanf("%lld%lld%lld",&n,&m,&P);

	if(m!=n-1)return printf("-1\n-1")&0;

	for(ll i=1;i<=m;i++){

		ll x,y;

		scanf("%lld%lld",&x,&y);

		addl(x,y);addl(y,x);

	}

	dp(1,1);

	for(ll i=1;i<=11;i++){

		ll p=v[1][i][0]|v[1][i][1]|v[1][i][2];

		if(!p)continue;

		printf("%lld\n%lld",i-1,(f[1][i][0]+f[1][i][1]+f[1][i][2])%P);

		break;

	}

	return 0;

}

巴特西

P4201-[NOI2008]设计路线【结论,树形dp】

正题

题目大意

解题思路

code

最新文章

热门文章