NOIP2018
P5024 保卫王国一颗树有 \(n\) 个点 \((1 \le n \le 10^5)\) , 带点权 。
给出 \(m\) 个询问 \((1 \le m \le 10^5)\) ，对于每个询问 ，你需要在树上选若干个点，满足如下条件：
[*]树上每一条边所连的两个节点中有至少一个被选中；
[*]限制询问相关的两个点必须被选中或不被选中；
要求你回答在满足上述条件的前提下，所选点点权的和的最小值，若无法满足上述条件则输出 \(-1\) 。
第一眼：要是没有条件 2 ，这就是一个骡的极小点覆盖集，再加上有 \(10^5\) 个询问，所以必然要使用倍增（或树剖）预处理。
考虑先不顾条件 2 ，考虑每个子树的根节点是否选的情况，用深搜做一遍子树点权和的DP；（然后就不晓得做了，果断贺 TJ ）
再进行一次深搜，处理出全树点权和减去当前子树点权和（同样也需考虑子树的根节点是否选的情况）
核心：随后处理出 \(ldp\) ，意为节点 u 与距其 \(2^n\) 的祖先所构成的链与其上的子树的最小权值和（后两个下标为判断链的两端是否被选）
https://img2022.cnblogs.com/blog/2214277/202206/2214277-20220626082553738-891249508.png
（如图，深搜第一次处理蓝色部分，第二次处理绿色部分，随后预处理链的情况，预计最多需 \(2 \log n\) 条小链构成图中红色的长链）
处理后分别解决每个询问，用 \(LCA\) 计算即可。时间复杂度 \(O(n \log n)\)
总结：这样的水体虽然是码农题，但是写一天实在是太过分了，要提高效率
code#include #define ll long long#define rgi register intusing namespace std;const int M=1e5+7;const int inf=1e11+7;inline int read(){ int w=0,r=1;char c=getchar(); while(!(isdigit(c)||c=='-'))c=getchar(); if(c=='-')r=-1,c=getchar(); while(isdigit(c))w=w*10+c-'0',c=getchar(); return w*r;}void gitgud(){ int ans=0; for(int i=1;i=0;i--) if(up!=up){ sta1=min(ldp+num1,ldp+num1); sta1=min(ldp+num1,ldp+num1); num1=sta1,num1=sta1; sta2=min(ldp+num2,ldp+num2); sta2=min(ldp+num2,ldp+num2); num2=sta2,num2=sta2; u1=up,u2=up; }// printf("st:%d %d %d %d%lld %lld\n",u1,s1,u2,s2,num1,num2); int lca=up; int an1=dp-dp-dp+num1+num2+ddp; int an2=dp-min(dp,dp)+min(num1,num1)-min(dp,dp)+min(num2,num2)+ddp;// printf("ed:%d %d %d %lld %lld %lld %lld %lld %lld\n",lca,u1,u2,an1,an2,num1,num1,num2,num2); return max(an1,an2);}int main(){//freopen("text.in","r",stdin);// freopen("text.out","w",stdout); n=read(),m=read(),read(); for(int i=1;i
页:
[1]