吉吉王国题解_牛客博客

本题是Rinne Loves Edges的变式，多了一个输出最大的切割长度
二叉苹果树题解：https://blog.nowcoder.net/n/c8a9812aa008472b8b31391e7995e29c

以下是错误题解，一开始做的时候我是这么做的：🤣🤣

跟二叉苹果树同样的思路，把边权下放到点权，这里不再赘述，跑一遍树的构造，再进行dfs记忆化dp。
边界是叶子结点，dp[叶子]=val[叶子]
其他结点，要么把儿子割掉，要么让儿子这颗子树已经割掉了叶子。
dp[root]=Σ min(val[son],dp[son])
本题注意事项：
1.需要两个dp数组存放，分别表示总长度和最长切割路
2.用总长度跟m进行比较，然后输出的是最长切割路

详情请看代码：

//下放边权变为点权，对于每一个子树，要么加上儿子的点权，要么加上儿子为结点的整个子树的dp值

#include <bits/stdc++.h>
using namespace std;
int n,m,s;
const int N=1010;
struct Edge
{
    int v,w,next;
}e[N<<1];
int cnt=0;
int head[N];
int val[N];
int dp[N];
int length[N];
bool haveson[N];
void add(int u,int v,int w)
{
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void pushdown(int root,int pre)
{
    for(int i=head[root];i;i=e[i].next)
    {
        int to=e[i].v;
        if(to==pre) continue;
        haveson[root]=true;
        pushdown(to,root);
        val[to]=e[i].w;
    }
}
void dfs(int root,int pre)
{
    if(!haveson[root]) length[root]=dp[root]=val[root];
    for(int i=head[root];i;i=e[i].next)
    {
        int to=e[i].v;
        if(to==pre) continue;
        dfs(to,root);
        dp[root]=max(dp[root],min(dp[to],val[to]));
        length[root]+=min(length[to],val[to]);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    pushdown(1,0);
    dfs(1,0);
    if(length[1]>m) printf("-1\n");
    else printf("%d\n",dp[1]);
}

错误的原因：直接向下贪心取边，dp记录的边和length记录的边有可能是不一样的！！！

那么就会导致这个数据是错误的：

4 10
1 2 10
2 3 5
2 4 6
感谢空白link 大佬提供的数据

我的代码会输出6，而真实的答案是10（因为同时取5和6，会超过m==10）

然而，单源最短路的做法也是不对的

会导致这个数据是错误的：

4 11
1 2 10
2 3 5
2 4 6
同样也是空白link 大佬提供的数据

这样会导致你的答案是10，而应当是6（此时同时取5和6，不会超过m==10）

那么怎样做才是正确的呢？由于答案是单调的，使用二分答案的方式即可

注意不存在的情况输出-1，就是在二分中，if语句的条件从来没有被满足过，即右端点r的值未被修改。

如何编写二分函数：

（dp数组保存的是切割的路中最长的一条，length数组保存的是切割的路的长度总和）

1.对于每个叶子结点，如果val[root]超过了当前二分的答案ans，那么dp[root]=length[root]＝无穷大

意思是，这个子树我不要去切割，那么以后取min的时候，肯定是把这个切割的任务交给了父亲或者他的某个祖先

2.对于非叶子结点，看一下切割子树的话，最长路会不会超过ans，超过的话肯定是不能取的，同理，看看切割自己和孩子

相连的这条边，会不会使最长路超过ans，会的话也是不能取的。

根据这个思路，就可以得到以下的代码（完整代码将在最后给出）：

        if(val[to]>ans&&dp[to]<=ans) {//只有子树合法
            dp[root]=max(dp[root],dp[to]);//用子树的dp值更新
            length[root]+=length[to];//加上子树的总长度
        }
        else if(dp[to]>ans&&val[to]<=ans) {//只有与孩子相邻的边合法
            dp[root]=max(dp[root],val[to]);//最长路肯定用孩子更新
            length[root]+=val[to];//总长度加上孩子
        }
        else if(dp[to]<=ans&&val[to]<=ans) {//两者都合法
            if(length[to]<val[to]) dp[root]=max(dp[root],dp[to]);
            else dp[root]=max(dp[root],val[to]);
            length[root]+=min(length[to],val[to]);
            //正常的使用两者中较小的累加到最长路，dp数组取哪个都无所谓
            //因为我只要看dp数组的值有没有比ans大即可，不需要管具体值
        }
        else {//两者都不行，赋一个最大值，把任务交给父亲或者其他祖先完成
            //如果追溯到根结点，任务依旧不能完成，就会导致length无穷大
            //那么二分的时候扩大左端点
            dp[root]=2000000;
            length[root]=2000000;
        }

最后，上二分模板直接把dp往里套，值得注意的是，每次二分清空dp数组和length数组

//下放边权变为点权，对于每一个子树，要么加上儿子的点权，要么加上儿子为结点的整个子树的dp值

#include <bits/stdc++.h>
using namespace std;
int n,m,s;
const int N=1010;
struct Edge
{
    int v,w,next;
}e[N<<1];
int cnt=0;
int head[N];
int val[N];
int dp[N];
int length[N];
bool haveson[N];
void add(int u,int v,int w)
{
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void pushdown(int root,int pre)
{
    for(int i=head[root];i;i=e[i].next)
    {
        int to=e[i].v;
        if(to==pre) continue;
        haveson[root]=true;
        pushdown(to,root);
        val[to]=e[i].w;
    }
}
void dfs(int root,int pre,int ans)
{
    if(!haveson[root])
    {
        if(val[root]<ans)
            length[root]=dp[root]=val[root];
        else length[root]=dp[root]=2000000;
    } 
    for(int i=head[root];i;i=e[i].next)
    {
        int to=e[i].v;
        if(to==pre) continue;
        dfs(to,root,ans);
        if(val[to]>ans&&dp[to]<=ans) {//只有子树合法
            dp[root]=max(dp[root],dp[to]);//用子树的dp值更新
            length[root]+=length[to];//加上子树的总长度
        }
        else if(dp[to]>ans&&val[to]<=ans) {//只有与孩子相邻的边合法
            dp[root]=max(dp[root],val[to]);//最长路肯定用孩子更新
            length[root]+=val[to];//总长度加上孩子
        }
        else if(dp[to]<=ans&&val[to]<=ans) {//两者都合法
            if(length[to]<val[to]) dp[root]=max(dp[root],dp[to]);
            else dp[root]=max(dp[root],val[to]);
            length[root]+=min(length[to],val[to]);
            //正常的使用两者中较小的累加到最长路，dp数组取哪个都无所谓
            //因为我只要看dp数组的值有没有比ans大即可，不需要管具体值
        }
        else {//两者都不行，赋一个最大值，把任务交给父亲或者其他祖先完成
            //如果追溯到根结点，任务依旧不能完成，就会导致length无穷大
            //那么二分的时候扩大左端点
            dp[root]=2000000;
            length[root]=2000000;
        }       
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    pushdown(1,0);
    int l=1,r=1010;
    int mid;
    while(l<r)
    {
        memset(dp,0,sizeof(dp));
        memset(length,0,sizeof(length));
        mid=(l+r)>>1;
        dfs(1,0,mid);
        if(length[1]<=m) r=mid;
        else l=mid+1;
    }
    if(r==1010) printf("-1\n");
    else printf("%d\n",l);
}

总结：本题具有迷惑性，可能会弄错，如果不理解需要反复理解，在阅读完题解以后自行编码提交。

吉吉王国 题解

吉吉王国题解