Codeforces 516D Drazil and Morning Exercise (栈、二分)

题目链接

https://codeforces.com/contest/516/problem/D

题解

我还是数据结构水平太低了啊……连一个点子树内距离不超过\(l\)的点数都不会求

首先有一个熟知的结论是，我们任取原树的一条直径，那么对于任何一个点，直径的两端点中至少有一个到它的距离等于它到所有点的最远距离。
假设直径是\((u_d,v_d)\), 那么我们就把\(u\)的最远距离的式子化简成了\(f_u=\max(dis(u,u_d),dis(u,v_d)\). 考虑\(u_d\)和\(v_d\)分别贡献给哪些点，可以发现一条特殊的边——直径的“中边”，设这条边是\((u_m,v_m)\)其中\(u_m\)离\(u_d\)更近，则这条边\(u_m\)一侧的所有点的\(f\)都是等于和\(v_d\)的距离，\(v_m\)一侧的所有点的\(f\)都等于和\(u_d\)的距离。
我们可以把上面的结论简化一下：以\(f_u\)最小的点\(u\)为根，则任何一个点的儿子的\(f\)值大于该点的\(f\)值，然后我们只需要求出每个点\(u\)子树内有多少个点\(f\)值不超过\(f_u+l\). 这样和上面显然是等价的，但是变简单了（不需要讨论两边子树）。
现在的问题就是如何对每个点\(u\)求出\(f_u\).
考虑每个点能贡献到哪里，在DFS时维护栈，由于栈上的元素\(f\)值是单调的，因此可以二分。注意双指针复杂度是错的。
时间复杂度\(O(qn\log n)\).
官方题解还给了一种\(O(qn\alpha(n)+n\log n)\)的并查集做法。

代码

#include<bits/stdc++.h> #define llong long long #define mkpr make_pair #define riterator reverse_iterator using namespace std;inline int read() {int x = 0,f = 1; char ch = getchar();for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}return x*f; }const int N = 1e5; struct Edge {int v,nxt; llong w; } e[(N<<1)+3]; int fe[N+3]; int fa[N+3]; llong dis[N+3]; int ans[N+3]; int stk[N+3]; int n,q,en,rt,diau,diav,tp; llong l;void addedge(int u,int v,int w) {en++; e[en].v = v; e[en].w = w;e[en].nxt = fe[u]; fe[u] = en; }void dfs1(int u,int tfa) {for(int i=fe[u]; i; i=e[i].nxt){int v = e[i].v; if(v==tfa) continue;dis[v] = dis[u]+e[i].w;dfs1(v,u);} } void dfs2(int u,int tfa) {for(int i=fe[u]; i; i=e[i].nxt){int v = e[i].v; if(v==tfa) continue;dis[v] = dis[u]+e[i].w;dfs2(v,u);} } void dfs3(int u,int tfa,llong tdis) {dis[u] = max(dis[u],tdis);for(int i=fe[u]; i; i=e[i].nxt){int v = e[i].v; if(v==tfa) continue;dfs3(v,u,tdis+e[i].w);} } void dfs4(int u) {stk[++tp] = u;int left = 0,right = tp;while(left<right){int mid = (left+right+1)>>1;if(dis[stk[mid]]<dis[u]-l) {left = mid;}else {right = mid-1;}} // printf("u=%d tp=%d pos=%d\n",u,tp,left);ans[u]++; ans[stk[left]]--;for(int i=fe[u]; i; i=e[i].nxt){int v = e[i].v; if(v==fa[u]) continue; fa[v] = u;dfs4(v);ans[u] += ans[v];}tp--; }int main() {scanf("%d",&n);for(int i=1; i<n; i++) {int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w);}dfs1(1,0);for(int i=1; i<=n; i++) {if(dis[i]>dis[diau]) {diau = i;}}dis[diau] = 0ll; dfs2(diau,0);for(int i=1; i<=n; i++) {if(dis[i]>dis[diav]) {diav = i;}}dfs3(diav,0,0ll);for(int i=1; i<=n; i++) {if(rt==0||dis[i]<dis[rt]) {rt = i;}}scanf("%d",&q);while(q--){scanf("%I64d",&l); for(int i=1; i<=n; i++) ans[i] = 0;dfs4(rt);int fans = 0; for(int i=1; i<=n; i++) fans = max(fans,ans[i]);printf("%d\n",fans);}return 0; }

总结

以上是生活随笔为你收集整理的Codeforces 516D Drazil and Morning Exercise (栈、二分)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。