[bzoj1316]树上的询问

树上的询问 bzoj-1316

题目大意：一棵n个点的带权有根树，有p个询问，每次询问树中是否存在一条长度为Len的路径，如果是，输出Yes否输出No.

注释：$1\le n\le 10^4$，$1\le p\le 100$，长度$\le 10^6$。

想法：有根树tm是啥意思？根在jb哪呢？老子我瞅tm这么半天也没看见根在哪呢？？这题点分治即可。我们用点分治的第二种：分别计算子树，然后用之前的信息更新答案。对于此题，我们可以直接维护一个set就行。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <set>

#define N 10010

using namespace std;

set<int>s;

int n,m,sum,root,cnt;

int a[N],dic[N<<1],size[N],mx[N],deep[N];

bool vis[N],ans[N];

int to[N<<1],head[N],val[N<<1],nxt[N<<1],tot;

inline void add(int x,int y,int z)

{

    to[++tot]=y;

    val[tot]=z;

    nxt[tot]=head[x];

    head[x]=tot;

}

void getroot(int pos,int fa)

{

    mx[pos]=0,size[pos]=1;

    for(int i=head[pos];i;i=nxt[i])

    {

        if(to[i]==fa||vis[to[i]]) continue;

        getroot(to[i],pos);

        size[pos]+=size[to[i]];

        mx[pos]=max(mx[pos],size[to[i]]);

    }

    mx[pos]=max(mx[pos],sum-size[pos]);

    if(mx[root]>mx[pos]) root=pos;

}

void getdeep(int pos,int fa)

{

    size[pos]=1;

    dic[++cnt]=deep[pos];

    for(int i=head[pos];i;i=nxt[i])

    {

        if(to[i]==fa||vis[to[i]]) continue;

        deep[to[i]]=deep[pos]+val[i];

        getdeep(to[i],pos);

        size[pos]+=size[to[i]];

    }

}

void dispose(int pos)

{

    // cout << " Fuck && Shit " << endl ;

    vis[pos]=true;

    s.clear();

    s.insert(0);

    for(int i=head[pos];i;i=nxt[i])

    {

        // cout << " Fuck 2" << endl ;

        if(vis[to[i]]) continue;

        cnt=0; deep[to[i]]=val[i],getdeep(to[i],0);

        for(int j=1;j<=cnt;j++)

        {

            for(int k=1;k<=m;k++)

            {

                if(s.find(a[k]-dic[j])!=s.end()) ans[k]=1;

            }

        }

        for(int j=1;j<=cnt;j++) s.insert(dic[j]);

    }

    for(int i=head[pos];i;i=nxt[i])

    {

        if(vis[to[i]]) continue;

        sum=size[to[i]];

        root=0;

        getroot(to[i],0);

        dispose(root);

        // cout << " Fuck " << endl ;

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    int x,y,c;

    for(int i=1;i<n;i++)

    {

        scanf("%d%d%d",&x,&y,&c);

        add(x,y,c),add(y,x,c);

    }

    // cout << "Fuck1" << endl ;

    for(int i=1;i<=m;i++)

    {

        scanf("%d",&a[i]);

        if(!a[i]) ans[i]=1;

    }

    mx[0]=1<<30;

    sum=n;

    // cout << "Fuck1" << endl ;

    getroot(1,0);

    // cout << "Fuck1" << endl ;

    dispose(root);

    // cout << "Fuck : " << m << endl ;

    for(int i=1;i<=m;i++)

    {

        printf("%s\n",ans[i]?"Yes":"No");

    }

    return 0;

}

小结：这种题更适合入门题。

巴特西

[bzoj1316]树上的询问_点分治

最新文章

热门文章