程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 5016 Mart Master II (樹上點分治)

HDU 5016 Mart Master II (樹上點分治)

編輯：關於C++

先兩遍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