求问思路正确性
查看原帖
求问思路正确性
929151
xxr___楼主2024/11/24 23:31

预处理 sonmaxuson_{max} u 表示 uu 子树内,maxvsonuvalue[u]+value[v]dis(u,v)2\max_{v\in son_u}^{value[u]+value[v]-dis(u,v)*2} outmaxuout_{max} u 表示子树外的那个式子,查询时分讨:

  • zzu,vu,v 简单路径上,那么 zz 一定取 maxvalue[z]\max value[z]
  • zzuu 子树内,那么答案就是 value[u]+value[v]+sonmaxudis(u,v)value[u]+value[v]+son_{max}u-dis(u,v)
  • vv 子树内同理
  • 可能在 lca(u,v)lca(u,v) 外,答案就是 value[u]+value[v]dis(u,v)+outmaxlca(u,v)value[u]+value[v]-dis(u,v)+out_{max}lca(u,v)
2024/11/24 23:31
加载中...