先兩遍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.disd[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
一個由印度人編寫的VC串口類，印度人vc串口軟件介紹
最早接觸回調函數應該是學sqlite數據庫時接觸到
POJ 2299 Ultra-QuickSort (歸並排序
CAEmitterCell 和 CAEmitterLayer
[cpp] /* * Copyright
經歷了一年有余的插件開發，
