先两遍DFS预处理出每个点距最近的基站的距离与基站的编号。 然后找重心，求出每个点距重心的距离，然后根据dis[x]+dis[y] < d[y]，用二分找出当前子树中不会被占领的数量，总点数减去即是被占领的数量。这样就可以求出每个点最多占领的点的数量。然后找最大值即可。 代码如下：
#include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 #define pi acos(-1.0) #pragma comment(linker, /STACK:1024000000) const int mod=1e9+7; const int INF=0x3f3f3f3f; const double eqs=1e-9; const int MAXN=100000+10; int head[MAXN], cnt, root, min1, tot; int siz[MAXN], vis[MAXN], d[MAXN], id[MAXN], ans[MAXN], dis[MAXN]; int color[MAXN]; struct node { int v, w, next; }edge[MAXN<<1]; void add(int u, int v, int w) { edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; } struct N { int dis, id; }F[MAXN]; bool cmp(N x, N y) { return x.dis d[v]+edge[i].w){ d[u]=d[v]+edge[i].w; id[u]=id[v]; } else if(d[u]==d[v]+edge[i].w) id[u]=min(id[u],id[v]); } } void dfs2(int u, int fa) { for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(v==fa) continue ; if(d[v]>d[u]+edge[i].w){ d[v]=d[u]+edge[i].w; id[v]=id[u]; } else if(d[v]==d[u]+edge[i].w){ id[v]=min(id[v],id[u]); } dfs2(v,u); } } void getsize(int u, int fa) { siz[u]=1; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(v==fa||vis[v]) continue ; getsize(v,u); siz[u]+=siz[v]; } } void getroot(int u, int fa, int s) { int max1=0; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(v==fa||vis[v]) continue ; getroot(v,u,s); max1=max(max1,siz[v]); } max1=max(max1,s-siz[u]); if(min1>max1){ min1=max1; root=u; } } void getdis(int u, int fa, int l) { dis[u]=l; F[tot].dis=d[u]-l; F[tot++].id=id[u]; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(v==fa||vis[v]) continue ; getdis(v,u,l+edge[i].w); } } int BS(int l, int u) { int low=0, high=tot-1, mid, ans=-1; while(low<=high){ mid=low+high>>1; if(F[mid].dis
?