P5024 [NOIP2018 提高组] 保卫王国
一颗树有 \(n\) 个点 \((1 \le n \le 10^5)\) , 带点权 。
给出 \(m\) 个询问 \((1 \le m \le 10^5)\) ，对于每个询问 ，你需要在树上选若干个点，满足如下条件：
- 树上每一条边所连的两个节点中有至少一个被选中；
- 限制询问相关的两个点必须被选中或不被选中；
要求你回答在满足上述条件的前提下，所选点点权的和的最小值，若无法满足上述条件则输出 \(-1\) 。
第一眼：要是没有条件 2 ，这就是一个骡的极小点覆盖集，再加上有 \(10^5\) 个询问，所以必然要使用倍增（或树剖）预处理。
考虑先不顾条件 2 ，考虑每个子树的根节点是否选的情况，用深搜做一遍子树点权和的DP；（然后就不晓得做了，果断贺 TJ ）
再进行一次深搜，处理出全树点权和减去当前子树点权和（同样也需考虑子树的根节点是否选的情况）
核心：随后处理出 \(ldp[g][0/1][0/1]\) ，意为节点 u 与距其 \(2^n\) 的祖先所构成的链与其上的子树的最小权值和（后两个下标为判断链的两端是否被选）
（如图，深搜第一次处理蓝色部分，第二次处理绿色部分，随后预处理链的情况，预计最多需 \(2 \log n\) 条小链构成图中红色的长链）
处理后分别解决每个询问，用 \(LCA\) 计算即可。时间复杂度 \(O(n \log n)\)
总结：这样的水体虽然是码农题，但是写一天实在是太过分了，要提高效率
code[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[u2]!=up[u1]){ sta1[0]=min(ldp[u1][0][0]+num1[0],ldp[u1][0][1]+num1[1]); sta1[1]=min(ldp[u1][1][0]+num1[0],ldp[u1][1][1]+num1[1]); num1[0]=sta1[0],num1[1]=sta1[1]; sta2[0]=min(ldp[u2][0][0]+num2[0],ldp[u2][0][1]+num2[1]); sta2[1]=min(ldp[u2][1][0]+num2[0],ldp[u2][1][1]+num2[1]); num2[0]=sta2[0],num2[1]=sta2[1]; u1=up[u1],u2=up[u2]; }// printf("st:%d %d %d %d %lld %lld\n",u1,s1,u2,s2,num1[s1],num2[s2]); int lca=up[0][u1]; int an1=dp[0][lca]-dp[1][u1]-dp[1][u2]+num1[1]+num2[1]+ddp[0][lca]; int an2=dp[1][lca]-min(dp[0][u1],dp[1][u1])+min(num1[0],num1[1])-min(dp[0][u2],dp[1][u2])+min(num2[0],num2[1])+ddp[1][lca];// printf("ed:%d %d %d %lld %lld %lld %lld %lld %lld\n",lca,u1,u2,an1,an2,num1[0],num1[1],num2[0],num2[1]); 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 |
