P4751 【模板】动态 DP(加强版)

    • 256通过
    • 2.6K提交
  • 题目提供者 shadowice1984
  • 评测方式 云端评测
  • 标签 Link-Cut Tree,LCT 动态规划,动规,dp 树链剖分,树剖 线段树 O2优化 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 2500ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    树剖常数小!跑不满!

    shadowice1984 为了向你证明他能卡树剖并且会卡树剖从而出了这道毒瘤题

    保证答案均在int范围内

    然后就被离线算法针对了……

    因此这道题变成了强制在线

    题目描述

    P4719

    给定一个 $n$ 个点的带点权树,进行 $m$ 次修改点权的操作

    你需要在每次修改之后输出树上最大带权独立集的权值之和

    输入输出格式

    输入格式:

    P4719

    第一行两个正整数 $n$ , $m$ 表示树的点数和总操作个数

    第二行n个整数 $V_{1}...V_{n}$ 表示每个点的点权

    接下来m行每行两个整数 $x,y$表示将x的点权修改为y

    对于第1行,x即为被操作的点的编号

    对于第2到m行,被操作的点的编号=x^lastans

    其中lastans是上一次操作后输出的答案,^表示按位异或操作

    输出格式:

    输出$m$行,第$i$行表示表示第$i$次操作之后树上最大带权独立集的权值和

    输入输出样例

    暂无测试点

    说明

    数据范围 $n \leq 1*10^6$,$m \leq 3*10^6$

    时限为标程的二倍,如果卡常数的话请使用int类型

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。