基本情况
打的还是挺不错的。一共做出来四道题，做出来四道题。这个 D 题是最后 A 的，D 题是最后 A 的。哎，D 题这个叫什么，稍微有点唐了，这漏了这两行有点唐了。还有这个 C 啊，读错题目了。这个 C 读错题目了，绷不住了，我自己给自己上难度啊，以为这个弹夹可以不打完就就换，这个弹夹可以不打完就换，自己给自己上难度。以后遇到这个题目啊，就是如果我们发现这道题目，就是我们还是要确定一下，就是一些限制条件，我们还是要想办法确定一下。
然后这个 d 的这个情况也是比较唐的，就这个 d 漏的这两行比较唐吧。是这样子，我感觉呢，以后这种如果说有多个，然后需要取 max 的话，最好啊 最好就是多整几行，多整几个变量，整个 add1 add2，这样子就你你不会忘记去给它进行这么一个赋值。然后你 add 1，你写出来，你不用，编译器还会报警，IDE 还会报警，对吧？你 add 1没用，你就知道你要把它取个 max 对吧？
https://codeforces.com/contest/2192
1 | if (a.id!=b.id) { |
心得感悟
下面是和队友对 D 题的这个探讨。
ZnZrYb: 02-22 00:36:59
首先是树上 dp
ZnZrYb: 02-22 00:37:38
auto dfs2=[&](auto && self,ll u,ll p,ll dep) -> void {
dep_ls[u]=dep;
set<Dep_sub> mx_diff_st;
set<A_sub> mx_a_st;
ll id=0;
ll add_mx=0;
for (auto to:g[u]) {
if (to==p) continue;
self(self,to,u,dep+1);
dp[u]+=dp[to];
dp[u]+=sum_a[to];
sum_a[u]+=sum_a[to];
add_mx=max(add_mx,ans_ls[to]-dp[to]);
mx_dep[u]=max(mx_dep[to],mx_dep[u]);
++id;
mx_diff_st.insert({id,mx_dep[to]-dep});
mx_a_st.insert({id,sum_a[to]});
}
if (id>=2) {
Dep_sub a=mx_diff_st.rbegin();
A_sub b=mx_a_st.rbegin();
ll add=0;
if (a.id!=b.id) {
add=a.dep*b.suma;
add_mx=max(add,add_mx);
}else {
a=prev(prev(mx_diff_st.end()));
add=a.depb.suma;
add_mx=max(add,add_mx);
a=*mx_diff_st.rbegin();
b=prev(prev(mx_a_st.end()));
add=a.depb.suma;
add_mx=max(add,add_mx);
}
}
ans_ls[u]=dp[u]+add_mx;
sum_a[u]+=A[u];
mx_dep[u]=max(dep,mx_dep[u]);
};
ZnZrYb: 02-22 00:37:54
答案在这个 ans
鵗曦: 02-22 00:39:12
我是先枚举移动各个节点，显然移动该节点最好办法就是移动到子树外的最深节点，移完之后贡献变化是高度差乘以子树的系数和
ZnZrYb: 02-22 00:39:19
具体来说就是这个增量可以从，就是子节点里面来，就是可以从子节点里面来。然后这个增量也可以就是我们自己来操作。自己来操作的话，是使用的 Max D I F F S T 和 Max A S T。其实就是把最大的 sum A 嫁接到最大的深度指数上。但如果说最大的深度指数和最大的 sum A 是同一个的话，需要稍微进行一下其他处理。
鵗曦: 02-22 00:39:29
然后每个节点的答案就是子树的最大值。
鵗曦: 02-22 00:40:10
我是这么想的，但是写不对。
鵗曦: 02-22 00:40:48
你觉得对不对
鵗曦: 02-22 00:40:51
[图片]
鵗曦: 02-22 00:41:14
diffst和ast是啥玩意
ZnZrYb: 02-22 00:42:13
diff_st 存的是子树深度差值。 AST 就是存的是子树权值和
ZnZrYb: 02-22 00:43:01
我觉得这个思路挺对的
鵗曦: 02-22 00:43:53
按我这么写，需要用的信息可以O（n）维护出来。唯一的难点就是要查子树外的最深节点
鵗曦: 02-22 00:44:02
然后咱想的是上个树剖
ZnZrYb: 02-22 00:44:15
啊
鵗曦: 02-22 00:44:24
因为一个子树在dfn上是连续的。
鵗曦: 02-22 00:44:37
所以可以查前面一整段和后面一整段，取其中的深度最大值。
鵗曦: 02-22 00:44:44
但是写的不对
鵗曦: 02-22 00:44:51
[图片]
ZnZrYb: 02-22 00:44:55
懂了
ZnZrYb: 02-22 00:45:50
那就上个 st 表都能解决
ZnZrYb: 02-22 00:46:03
感觉挺对的
鵗曦: 02-22 00:46:13
过不去样例
鵗曦: 02-22 00:46:16
写炸了
ZnZrYb: 02-22 00:46:21
[笑哭]
鵗曦: 02-22 00:46:57
dfn序列用st表预处理是吧
鵗曦: 02-22 00:47:14
咱的树剖板子默认写了线段树
ZnZrYb: 02-22 00:47:22
哦，我知道你可能是哪里的问题了
鵗曦: 02-22 00:47:41
哪里
ZnZrYb: 02-22 00:48:34
不过我不确定，就是你限定了树的范围了吧，就是他求的是 i 的子树
ZnZrYb: 02-22 00:48:38
的答案
鵗曦: 02-22 00:49:16
不是输出每个节点对应的答案吗
鵗曦: 02-22 00:49:26
每个节点的操作是可以任意选择它指数里面的一个节点进行嫁接
鵗曦: 02-22 00:49:34
子树
鵗曦: 02-22 00:49:57
所以每个节点的答案就是处理出来的子树里的最大值。
ZnZrYb: 02-22 00:51:36
感觉好像你没有理解错啊，你也是查询的子树里深度最大值是吧
鵗曦: 02-22 00:52:09
我已经枚举计算过了，假如要移动某某个节点，能产生的最大权重
鵗曦: 02-22 00:52:35
所以输出答案的时候，对于一个节点的答案，只需要找这个节点所在的子数里面计算出的各个最大权重中的最大
鵗曦: 02-22 00:52:47
当然也是O（n）就能弄出来的。
ZnZrYb: 02-22 00:53:41
子树里面的这个点，是连到子树里面，还是连到子树外面
ZnZrYb: 02-22 00:54:22
如果计算 i 的答案，子树 i 里面的点必须只能连接到子树 i 的里面的其他点
鵗曦: 02-22 00:54:34
6
鵗曦: 02-22 00:54:37
这里理解错了
鵗曦: 02-22 00:55:15
那我这样反着做错完了。