Boatherds POJ

题意：

给出一棵 (n) 个点的树，(m) 次询问，每次询问长度为 (x) 的简单路径是否存在。
数据范围：(1 leq N leq 10^4,M leq 100,1 leq x_i leq 10^7)

分析：

点分治。
先把所有的询问存起来，离线处理。每次计数时，要注意。具体见 (solve) 函数。
一开始一直 (T)，发现原来是找重心时，忘了写 (dfs(u,v))；
后来(WA) ，因为存的是单向边。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int N=1e4+5;
int q[105],ans[105],dis[N];
int sz[N],num,w,qn,minn;
bool vis[N];
P a[N];
struct edge
{
    int to,nxt,len;
}e[N<<1];
int head[N],cot;
void init()
{
    memset(head,-1,sizeof(head));
    cot=1;
    memset(vis,false,sizeof(vis));
    memset(ans,0,sizeof(ans));
}
void addedge(int from,int to,int len)
{
    e[cot].to=to;
    e[cot].len=len;
    e[cot].nxt=head[from];
    head[from]=cot++;
}
void dfs(int v,int p)//重心
{
    sz[v]=1;
    int res=0;
    for(int i=head[v];i!=-1;i=e[i].nxt)
    {
        int u=e[i].to;
        if(vis[u]||u==p)
            continue;
        dfs(u,v);
        sz[v]+=sz[u];
        res=max(res,sz[u]);
    }
    res=max(res,num-sz[v]);
    if(res<minn)
    {
        minn=res;
        w=v;
    }
}
void dfs2(int v,int p,int d,int &cnt)
{
    dis[++cnt]=d;
    for(int i=head[v];i!=-1;i=e[i].nxt)
    {
        int u=e[i].to;
        if(vis[u]||p==u)
            continue;
        dfs2(u,v,d+e[i].len,cnt);
    }
}
void solve(int v,int d,int f)
{
    int cnt=0,p=0;
    dfs2(v,v,0,cnt);
    sort(dis+1,dis+1+cnt);
    dis[0]=-1;
    for(int i=1;i<=cnt;i++)
    {
        if(dis[i]==dis[i-1])
            a[p].second++;
        else
        {
            a[++p].first=i;
            a[p].second=1;
        }
    }
    for(int i=1;i<=qn;i++)
    {
        int l=1,r=p;
        while(l<=r)
        {
            int t=dis[a[l].first]+dis[a[r].first]+2*d;
            if(t<q[i])
                l++;
            else if(t>q[i])
                r--;
            else
            {
                if(l==r)
                    ans[i]+=f*(a[l].second*(a[l].second-1)/2);
                else
                    ans[i]+=f*(a[l].second*a[r].second);
                l++,r--;
            }
        }
    }
}
void divide(int v,int p)
{
    solve(v,0,1);
    vis[v]=1;
    for(int i=head[v];i!=-1;i=e[i].nxt)
    {
        int u=e[i].to;
        if(vis[u]||p==u)
            continue;
        solve(u,e[i].len,-1);
        num=sz[u],minn=N;
        dfs(u,v);
        divide(w,w);
    }
}
int main()
{
    int n,d,c,x;
    while(scanf("%d",&n),n)
    {
        init();
        for(int i=1;i<=n;i++)
        {
            while(scanf("%d",&d),d)
            {
                scanf("%d",&c);
                addedge(i,d,c);
                addedge(d,i,c);
            }
        }
        qn=0;
        while(scanf("%d",&x),x)
            q[++qn]=x;
        minn=N,num=n;
        dfs(1,1);
        divide(w,w);
        for(int i=1;i<=qn;i++)
            printf("%s
",ans[i]>0?"AYE":"NAY");
        printf(".
");
    }
    return 0;
}