CF516D Drazil and Morning Exercise【2019集训队作业 】

CF516D Drazil and Morning Exercise【2019集训队作业 】

注意 $f_x$ 是对全局的而不是对一个连通块。

不然就不可做了2333（是我太菜了不会做

所以可以先把所有 $f_x$ 求出来。

然后观察它的性质可以发现，

以 $f_x$ 最小的点为根的树，满足任意一个节点 $u$ 的所有孩子节点的 $f_x$ 都小于 $f_u$ 。

然后就很好做了。

按照 $f_x$ 大到小枚举每个节点，考虑把这个节点的 $f_x$ 当作 m i n { f x } min\{f_x\} min{ fx?} ，把不合法的点删掉。

你会发现显然这样做是对的，因为枚举的时候 $f_x$ 单调，删了的点不会变合法。

然后就做完咯。$O(n\log n+qn\alpha (n))$ 。

#include<bits/stdc++.h>
#define re register
#define LL long long
#define lb(x) ((x)&(-x))
#define max(a,b) ((a)>(b)?(a):(b))
inline int read() {
    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int maxn=1e5+5;
struct E{
    int v,nxt,w;}e[maxn<<1];
int n,m,num,Rt,rt,sz,S;
int head[maxn],sum[maxn],son[maxn],pos[maxn],dep[maxn],d[maxn],Ans[55];
LL pre[maxn],mx[maxn],q[55],c[maxn];
inline void add(int x,int y,int w) {
    e[++num].v=y;e[num].nxt=head[x];head[x]=num;e[num].w=w;
}
inline int find(LL x) {
    int l=1,r=sz,now=0;while(l<=r) {
    int mid=l+r>>1;if(c[mid]<=x) now=mid,l=mid+1;else r=mid-1;}return now;
}
void dfs(int x,int fa) {
    for(re int i=head[x];i;i=e[i].nxt) {
    if(e[i].v==fa) continue;pre[e[i].v]=pre[x]+e[i].w;dfs(e[i].v,x);}
}
void dfs1(int x) {
    sum[x]=1;for(re int i=head[x];i;i=e[i].nxt) {
    if(dep[e[i].v]) continue;dep[e[i].v]=dep[x]+1;dfs1(e[i].v);sum[x]+=sum[e[i].v];if(sum[e[i].v]>sum[son[x]]) son[x]=e[i].v;}
}
inline void add(int x,int v) {
    for(re int i=x;i<=sz;i+=lb(i)) d[i]+=v;
}
inline int ask(int x) {
    int now=0;for(re int i=x;i;i-=lb(i)) now+=d[i];return now;
}
void calc(int x,int o) {
    add(pos[x],o);for(re int i=head[x];i;i=e[i].nxt)if(dep[e[i].v]>dep[x]&&S!=e[i].v) calc(e[i].v,o);
}
void dsu(int x,int k) {
    for(re int i=head[x];i;i=e[i].nxt) if(dep[e[i].v]>dep[x]&&son[x]!=e[i].v) dsu(e[i].v,0);if(son[x]) dsu(son[x],1);S=son[x],calc(x,1),S=0;for(re int i=1;i<=m;i++) {
    int g=ask(find(mx[x]+q[i]));Ans[i]=max(Ans[i],g);}if(!k) calc(x,-1);
}
int main() {
    n=read();for(re int x,y,w,i=1;i<n;++i)x=read(),y=read(),w=read(),add(x,y,w),add(y,x,w);m=read();for(re int i=1;i<=m;i++) scanf("%lld",&q[i]);dfs(1,0);rt=1;for(re int i=2;i<=n;i++) if(pre[i]>pre[rt]) rt=i;pre[rt]=0;dfs(rt,0);Rt=1;for(re int i=1;i<=n;i++) mx[i]=pre[i];for(re int i=2;i<=n;i++) if(pre[i]>pre[Rt]) Rt=i;pre[Rt]=0;dfs(Rt,0);for(re int i=1;i<=n;i++) mx[i]=max(mx[i],pre[i]);rt=1;for(re int i=2;i<=n;i++) if(mx[i]<mx[rt]) rt=i;dep[rt]=1;dfs1(rt);for(re int i=1;i<=n;i++) c[i]=mx[i];std::sort(c+1,c+n+1);sz=std::unique(c+1,c+n+1)-c-1;for(re int i=1;i<=n;i++) pos[i]=find(mx[i]);dsu(rt,1);for(re int i=1;i<=m;i++) printf("%d\n",Ans[i]);return 0;
}