BZOJ 1460: Pku2114 Boatherds 点分治

Description
给你一棵n个点的带权有根树，有p个询问，每次询问树中是否存在一条长度为Len的路径，如果是，输出Yes否输出No.
Input
第一行两个整数n, p分别表示点的个数和询问的个数．接下来n-1行每行三个数x, y, c，表示有一条树边x→y，长度为c．接下来p行每行一个数Len，表示询问树中是否存在一条长度为Len的路径．
Output
输出有p行，Yes或No.
Sample Input
6 4

1 2 5

1 3 7

1 4 1

3 5 2

3 6 3

Sample Output
Yes

Yes

【数据范围】

30%的数据，n≤100．

100%的数据，n≤10000，p≤100，长度≤100000．

和POJ题目一样？？？我在POJ 可以AC,BZOJ死活AC不了啊，有路过A了的大神求助。下面的代码在POJ能

AC。

只需将“不超过k”改为“不超过k减去小于k”，就可以得到“等于k”的数量了。

///BZOJ 1460

#include <vector>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 10010;
typedef long long LL;
struct edge
{
    int to;
    LL length;
};
int n,k;
vector<edge>G[maxn];
bool centroid[maxn];///顶点是否已作为重心删除的标记
int subtree_size[maxn];///以该顶点为根的子树的大小(查找重心时用)
LL ans;
///以该顶点为根的子树的大小(查找重心时用)
int compute_subtree_size(int v, int p)
{
    int c=1;
    for(int i=0; i<G[v].size(); i++)
    {
        int w=G[v][i].to;
        if(w==p||centroid[w]) continue;
        c+=compute_subtree_size(G[v][i].to, v);
    }
    subtree_size[v]=c;
    return c;
}
///查找重心的递归函数，t是整个连通分量的大小
///在以v为根的子树中寻找一个顶点，使得删除该顶点后最大子树的顶点数最小
///返回值为pair(最大子树的顶点数，顶点编号)
pair<int, int>search_centroid(int v, int p, int t)
{
    pair<int, int>res = make_pair(0x3f3f3f3f, -1);
    int s=1, m=0;
    for(int i=0; i<G[v].size(); i++)
    {
        int w=G[v][i].to;
        if(w==p||centroid[w]) continue;
        res = min(res, search_centroid(w, v, t));
        m=max(m, subtree_size[w]);
        s+=subtree_size[w];
    }
    m=max(m,t-s);
    res=min(res,make_pair(m,v));
    return res;
}
void enumerate_paths(int v, int p, int d, vector<int>&ds)
{
    ds.push_back(d);
    for(int i=0; i<G[v].size(); i++)
    {
        int w=G[v][i].to;
        if(w==p||centroid[w]) continue;
        enumerate_paths(w, v, d+G[v][i].length, ds);
    }
}
int count_pairs(vector<int>&ds)
{
    int res=0;
    sort(ds.begin(),ds.end());
    int j=ds.size();
    for(int i=0; i<ds.size(); i++)
    {
        while(j>0&&ds[i]+ds[j-1]>k) j--;///除去和本身组成的点对
        res+=j-(j>i?1:0);
    }
    j=ds.size();
    for(int i=0; i<ds.size(); i++)
    {
        while(j>0&&ds[i]+ds[j-1]>=k) j--;
        res-=j-(j>i?1:0);
    }
    return res;
}
void solve_subproblem(int v)
{
    compute_subtree_size(v,-1);
    int s=search_centroid(v,-1,subtree_size[v]).second;
    centroid[s] = true;
    ///统计按顶点s分割后子树中的对数
    for (int i = 0; i < G[s].size(); i++)
    {
        if (centroid[G[s][i].to])
            continue;
        solve_subproblem(G[s][i].to);
    }
    ///统计经过点s的对数
    static vector<int> ds;
    ds.clear();
    ds.push_back(0);
    for (int i = 0; i < G[s].size(); i++)
    {
        if (centroid[G[s][i].to])
            continue;
        static vector<int> tds;
        tds.clear();
        enumerate_paths(G[s][i].to, s, G[s][i].length, tds);
        ans -= count_pairs(tds);
        ds.insert(ds.end(), tds.begin(), tds.end());
    }
    ans += count_pairs(ds);
    centroid[s]=false;
}


int main()
{
    int p;
    while(scanf("%d%d", &n,&p)!=EOF){
        for(int i=0; i<n; i++) G[i].clear();
        for(int i=1; i<n; i++){
            int u, v;
            LL c;
            scanf("%d%d%lld", &u,&v,&c);
            G[u-1].push_back({v-1,c});
            G[v-1].push_back({u-1,c});
        }
        while(p--){
            scanf("%d", &k);
            ans=0;
            memset(centroid, 0, sizeof(centroid));
            solve_subproblem(0);
            if(ans>0) puts("Yes\n");
            else puts("No\n");
        }
    }
    return 0;
}