题解

T1：华丽转身
Task1:14 20分
可以观察到数据即小，可以使用DFS通过（其他乱搞也可）
（为了方便讲解，此处先讲解task3）
Task3:912 另20分
可以发现在权值为1的情况下，可以使用贪心（后文将证明），记录下上一次的名次last，每次都贪心的尽量让名次最大（即last/2），若l>last/2，则说明不管怎样都无法满足条件，则将排名设为r
由于贪心遗漏的情况是当l<=last/2时取r通过舍弃这一次的奖品来使下一次获得奖品，而由于权值全部为1，所以本次贪心所选取的补偿了下一个没取到的，所以贪心正确性可证，时间复杂度O(n)
Task2: 56&78 20分（可获得40分）
由上文可知，本题需要使用dp来解决，所以考虑直接设计状态f[i][j]表示第i场考试考第j名时最多的奖品数，则状态转移方程为f[i][j]=max(f[i-1][1],f[i-1][j/2]+num[i])
，显然当i一定时，f[i][j]具有单调性，复杂度O()
Task4:13~20 40分（可获得100分）
发现m只有10^18，所以连续获奖的次数最多只有log2m=64次，同时受上文贪心思想的启发，易发现当本次能获得奖品时取last/2最优，否则取r最优。则可设计状态f[i][j]表示第i场考试时已经连续获得了j次奖的最多奖品数，则状态转移方程为f[i][j]=f[i-1][j-i]+numi
g[i][j]=min(max(l[i],g[i-1][j-1]/2) ,r[i])(g[i-1][j-1]/2<=r[i])
其中g[i][j]为辅助数组，表示连续去j次奖后第i场考试的最大名次，在转移过程中由上述贪心即可求出g数组，而最大值可在上一轮循环的计算中求出，即f[i][j]可以O(1)求出，由于每取一次奖，能取得名次都会缩小为原来的1/2,即j的规模只有log2m,故复杂度为O()
ps：可以使用滚动数组优化空间，本题没有卡空间，所以可以不使用
T2：交通网络
Task1:30分
只需依题目要求操作即可
Task2:对于另20分（可获得50分）
保证没有2,3操作，数据范围200000，我们需要一个单次操作logn的算法来实现，路径加操作易想到差分，通过将路径拆分为两段进行维护
Task3:对于另30分（可获得80分）
此时没有3操作，由于只需要在最后输出权值，可以想到离线维护，先将所有需要加的点读入进来建树，再如上操作
另：每次加入一个点时，将它的边建好，其他需要的信息维护好也可以实现动态维护这个操作
Task4:40分（100分）
根据上面的思路，可以考虑离线处理本题，可以发现对于3操作，删去节点后始终保证树的连通，隐藏含义即为删去的都是当前树的叶子节点，所以后面增加的点提前加上并不影响前面的修改操作，故只需要先将所有操作读进来，将所有的加入，再标记出已删除的点，判断哪些点仍在树上即可。
时间复杂度O(mlogn)，若使用tarjan求LCA可以优化至O(m)
T3：树
设sumi表示每一个vi的到根求和。因为sum[x]=sum[fa[x]]+v[x],所以v[x]>=0等价于sum[fa[x]]>= sum[x]。同时题目中的每次操作就相当于直接将sum[x]加上k
于是原问题就等价于每次可以直接单点修改sumx，求使得 “任意两个节点i,j，若i为j的祖先，则有sumi<=sumj”的最小修改次数
做法一：（30分）
设fij表示i的子树中最小权值为j的最大子集
转移fxi=fyj+[sumx<=j]
做法二：（60分）
在刚刚的基础上优化一下dp的定义
设fij表示i的子树中最小权值>=j的最大子集
转移fxi=fyi+[sumx<=i]
最后在f自己进行更新
做法三：（100分）
可以将上述方法差分后在用线段树合并解决，不过这里我着重讲做法四
做法四：（100分）
由于每个点只会被修改1次，求最小修改次数就等价于n-求最多不被修改的点数
考虑一种贪心方案，我们让子树内最小点权尽量大，为新来的点留位置 二分优化 LIS,现在我们依然二分，然后因为多线程合并采用启发式合并套一个有序的结构 multiset即可
最后由于这样并不能保证1号节点>=0所以加入一个虚根0令sum0=0且建边0->1即可