poj 2114 Boatherds 树的分治

还是利用点的分治的办法来做，统计的办法不一样了，我的做法是排序并且标记每个点属于哪颗子树。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn=1e4+9;

int head[maxn],lon,n,mm,m;

struct

{

    int next,to,w;

}e[maxn<<1];

void edgeini()

{

    memset(head,-1,sizeof(head));

    lon=0;

}

void edgemake(int from,int to,int w)

{

    e[++lon].to=to;

    e[lon].w=w;

    e[lon].next=head[from];

    head[from]=lon;

}

int son[maxn],maxson[maxn];

bool use[maxn];

int dp(int t,int from)

{

    int ans,tmp,now=1e4+9;

    son[t]=maxson[t]=0;

    for(int k=head[t];k!=-1;k=e[k].next)

    {

        int u=e[k].to;

        if(u==from||use[u]) continue;

        tmp=dp(u,t);

        if(maxson[tmp]<now)

        {

            now=maxson[tmp];

            ans=tmp;

        }

        son[t]+=son[u];

        maxson[t]=max(son[u],maxson[t]);

    }

    son[t]++;

    maxson[t]=max(maxson[t],mm-son[t]);

    if(maxson[t]<now) ans=t;

    return ans;

}

int d[maxn],top;

struct D

{

    int data,ss;

    bool operator <(const D & xx) const

    {

        return data<xx.data;

    }

}a[maxn];

void dfs(int t,int from)

{

    a[++top].data=d[t];

    son[t]=0;

    for(int k=head[t];k!=-1;k=e[k].next)

    {

        int u=e[k].to;

        if(u==from||use[u]) continue;

        d[u]=d[t]+e[k].w;

        dfs(u,t);

        son[t]+=son[u];

    }

    son[t]++;

}

int ss[maxn];

int cal(int l,int r)

{

    int ret=0;

    for(;l<r;)

    {

        while(r>l&&a[l].data+a[r].data>m) r--;

        while(r>l&&a[l].data+a[r].data<m) l++;

        if(a[l].data+a[r].data==m)

        {

            int ll=a[l].ss,rr=a[r].ss;

            if(ll!=rr) return true;

            while(l<r&&a[l+1].data==a[l].data)

            {

                if(a[l+1].ss!=ll) return true;

                l++;

            }

            while(l<r&&a[r-1].data==a[r].data)

            {

                if(a[r-1].ss!=rr) return true;

                r--;

            }

            l++;

            r--;

        }

    }

    return false;

}

bool solve(int t)

{

    int now=dp(t,0);

    use[now]=1;

    d[now]=top=0;

    dfs(now,0);

    int tmp=2,con=0;

    for(int k=head[now];k!=-1;k=e[k].next)

    {

        int u=e[k].to;

        if(use[u]) continue;

        con++;

        for(int i=tmp;i<tmp+son[u];i++)

        a[i].ss=con;

        tmp+=son[u];

    }

    sort(a+1,a+tmp);

    a[1].ss=0;

    int ret=cal(1,tmp-1);

    if(ret) return true;

    for(int k=head[now];k!=-1;k=e[k].next)

    {

        int u=e[k].to;

        if(use[u]) continue;

        mm=son[u];

        if(solve(u)) return true;

    }

    return false;

}

int main()

{

//    freopen("in.txt","r",stdin);

    while(scanf("%d", &n)!=EOF&& n)

    {

        edgeini();

        for(int i=1,to,w;i<=n;i++)

        {

            while(scanf("%d",&to),to)

            {

                scanf("%d",&w);

                edgemake(i,to,w);

                edgemake(to,i,w);

            }

        }

        int tmp;

        while(scanf("%d",&tmp)!=EOF&&tmp)

        {

            m=tmp;

            mm=n;

            memset(use,0,sizeof(use));

            if(solve(1))

            printf("AYE\n");

            else

            printf("NAY\n");

        }

        printf(".\n");

    }

    return 0;

}