题解 P3806 【【模板】点分治1】

Bang_Dream · 2017-07-09 23:08:45 · 题解

<center>发题解抢一血

这题和树上的路径有关，点分治就立马套上

但是不能对每个输入的k都点分治一遍，这样得分好像是T60

于是乎点分治一遍，统计出每种路径长度的方案数，k<=10000000，数组勉强开下。

每次讯问时，查表出解。

对于这题，题目描述有误，输出的NYE实为NAY。

接下来是代码

%:pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
const int N=10010,INF=1e9,K=10000001;
int n,k,x,y,z,minn,size,root,b[N<<1],c[N<<1],ne[N<<1],fi[N],son[N],tot,m,d[N],num[K];
bool done[N];
inline void add(int x,int y,int z){
    b[++k]=y; c[k]=z; ne[k]=fi[x]; fi[x]=k;
}
inline int max(int x,int y){
    return x>y?x:y;
}
void getroot(int x,int fa){
    son[x]=1;
    int bal=0;
    for (int j=fi[x]; j; j=ne[j])
    if (b[j]!=fa&&!done[b[j]]){
        getroot(b[j],x);
        son[x]+=son[b[j]];
        bal=max(bal,son[b[j]]);
    }
    bal=max(bal,size-son[x]);
    if (bal<minn) minn=bal,root=x;
}
void getdeep(int x,int fa,int deep){
    d[tot++]=deep;
    for (int j=fi[x]; j; j=ne[j])
    if (b[j]!=fa&&!done[b[j]]) getdeep(b[j],x,deep+c[j]);
}
void calc(int now,int ind,int init){
    tot=0;
    getdeep(now,now,0);
    for (int i=0; i<tot; i++)
    for (int j=0; j<tot; j++)
    if (ind&&d[i]+d[j]<=K) ++num[d[i]+d[j]]; else if (d[i]+d[j]+init<=K) --num[d[i]+d[j]+init];
}
void work(int x){
    calc(x,1,0);
    done[x]=1;
    for (int j=fi[x]; j; j=ne[j])
    if (!done[b[j]]){
        calc(b[j],0,c[j]*2);
        minn=INF; size=son[b[j]]; getroot(b[j],x);
        work(root);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n-1; i++) scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);
    minn=INF; size=n; getroot(1,1);
    work(root);
    for (int i=1; i<=m; i++){
        scanf("%d",&k);
        if (num[k]) printf("AYE\n"); else printf("NAY\n");
    }
    return 0;
}