关于下午 T1 的新思路,但是炸了,求问
  • 板块学术版
  • 楼主XingnoYi
  • 当前回复9
  • 已保存回复9
  • 发布时间2025/6/28 20:07
  • 上次更新2025/6/29 14:27:54
查看原帖
关于下午 T1 的新思路,但是炸了,求问
735797
XingnoYi楼主2025/6/28 20:07

对于操作二,赛时想到了一种树形 DP 的做法,但是交上去不对,求问是哪里有问题。

// 这是初始化
#define big long long
big dp[100005]; // dp[i] 表示以 i 为根的子节点中编号最小的那一个 
// 一开始初始化为极大值
void dfs(big u,big fa)
{
    big flag = 1;
    for(big i = head[u];i ;i = edge[i].next)
    {
        big v = edge[i].to;
        if(v == fa) continue;
        flag = 0;
        dfs(v,u);
        dp[u] = min({dp[v],v,dp[u]});
    }
    if(flag) // 叶子结点
    {
        dp[u] = u;
    }
}
2025/6/28 20:07
加载中...