BZOJ1063 NOI2008 道路设计树形DP

题目传送门：

题意精简版：给出一棵树，在一种方案中可以将树的若干链上的所有边的边权改为$0$，但需要保证任意两条链之间没有交点。问最少的一种方案，使得从根节点到其他节点经过的边的边权和的最大值最小，并求出方案数。$N \leq 10^5$

真心火题，现在我还在想是哪个神人推出的这个DP方程

关于原题中的无解情况直接判断$M==N-1$是否成立即可，因为根据题目要求，最后生成出来的一定会是一棵树。

先考虑第二问，设$f_{i,j,k}$表示在子树$i$内，最大的边权和不超过$j$，点$i$与其$k$个儿子在一条链上的方案数。首先可以知道$k=0,1,2$，因为任意两条链之间没有交点。

接下来我们考虑$j$的取值。手玩可以发现，当一棵树是三叉树的时候，才会有一个边权的贡献，而当整棵树是深度为$h$的满二叉树的时候，才会有$h$的最大边权，而$\sum\limits_{i=0}^{10} 3^i = 8.6 \times 10^4$，所以可以知道答案会小于等于10，所以$j$的有效取值范围就在$[0,10]$中间，第一问的答案自然也就很小。

接下来考虑转移。根据乘法原理，我们可以得到这样子的式子：

$$f_{i,j,2}=f_{i,j,1} \times (f_{soni,j,0} + f_{soni,j,1}) + f_{i,j,2} \times (f_{soni,j-1,0} + f_{soni,j-1,1} + f_{soni,j-1,2})$$

$$f_{i,j,1}=f_{i,j,0} \times (f_{soni,j,0} + f_{soni,j,1}) + f_{i,j,1} \times (f_{soni,j-1,0} + f_{soni,j-1,1} + f_{soni,j-1,2})$$

$$f_{i,j,0}=f_{i,j,0} \times (f_{soni,j-1,0} + f_{soni,j-1,1} + f_{soni,j-1,2})$$

其中$soni$表示$i$的某个儿子。边界是$f_{i,j,0}=1$，其余为$0$

每一个点统计儿子的所有转移即可，复杂度为$O(33N)$。

至于第一问，可以从小到大枚举dp的第$2$维，最小的在$1$号点上方案数大于$0$的数就是答案。

注意：因为原题需要$mod\,Q$，所以如果答案$mod\,Q==0$会出现错误，推荐在某个数与$mod \, Q = 0$时将其修改为$Q$而不是$0$。

 #include<bits/stdc++.h>
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     while(!isdigit(c))
         c = getchar();
     while(isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return a;
 }

 ;
 struct Edge{
     int end , upEd;
 }Ed[MAXN << ];
 int head[MAXN] , fa[MAXN] , cntEd , N , M , Q;
 ][];
 bool vis[MAXN];

 inline void addEd(int a , int b){
     Ed[++cntEd].end = b;
     Ed[cntEd].upEd = head[a];
     head[a] = cntEd;
 }

 inline int get(long long x){
      && x % Q ==  ? Q : x % Q;
 }

 void dfs(int now){
     vis[now] = ;
      ; i <=  ; i++)
         dp[now][i][] = ;
     for(int i = head[now] ; i ; i = Ed[i].upEd)
         if(!vis[Ed[i].end]){
             fa[Ed[i].end] = now;
             dfs(Ed[i].end);
         }
      ; j <=  ; j++){
         ][] + dp[now][j - ][] + dp[now][j - ][]) , l = ] + dp[now][j][]);
         dp[fa[now]][j][] = ] * l + dp[fa[now]][j][] * k);
         dp[fa[now]][j][] = ] * k + dp[fa[now]][j][] * l);
         dp[fa[now]][j][] = ] * k);
     }
     dp[fa[now]][][] = ][] * (dp[now][][] + dp[now][][]));
     dp[fa[now]][][] = ][] * (dp[now][][] + dp[now][][]));
     dp[fa[now]][][] = ;
 }

 int main(){
     N = read();
     M = read();
     ){
         cout << "-1\n-1";
         ;
     }
     Q = read();
      ; i <= M ; i++){
         int a = read() , b = read();
         addEd(a , b);
         addEd(b , a);
     }
     dfs();
      ; i <= N ; i++){
         ][i][] + dp[][i][] + dp[][i][];
         if(sum){
             cout << i << endl << sum % Q;
             ;
         }
     }
 }

巴特西

BZOJ1063 NOI2008 道路设计树形DP

最新文章

热门文章

巴特西

BZOJ1063 NOI2008 道路设计 树形DP

最新文章

热门文章

BZOJ1063 NOI2008 道路设计树形DP