题干

给定一棵有 n 个点的树，询问树上距离为 k的点对是否存在。

分析

Part1：点分治的意义

 分治都懂吧，将问题划分为若干个子问题，最后合并答案

可以类比归并排序，冒泡排序的复杂度为O(n^2)，而归并则是稳定的O(n log2 n)

点分治同理，我们将每个树划分为若干个子树，然后分开来处理，这样可以优化时间复杂度

Part2：如何点分治

观察若有这样一棵树，若我们把1当做根节点，则点分治就毫无意义

因为这时候我们的递归层数为n层

时间复杂度仍然是O(n^2)

但如果看做这样一棵树呢？

 显然，若按照根节点分割开后，剩下的子树为12,45每一颗树的大小缩小为原来的一半

所以递归的层数直接降为 log2 n 层

可以得到现在的复杂度仅有O(n log2 n)

那么我们怎么找到要切割的这个点呢？

显然是树的重心，这样分割完后剩下的子树会尽量地平衡（size的最大会最小），从而达到最优的时间复杂度

Part 3：如何操作

对于一棵树，该树上的所有路径必能分为：

1.经过根节点的路径

2.没经过根节点的路径

情况1：

先考虑第一种情况：我们对每一个根（也就是重心），我们求取他所有的dis[k]表示k到根的距离

那么任意两点的距离（经过根）distance(x,y)=dis[x]+dis[y]

对于一个询问k，若存在dis[x]和dis[y]=k-dis[x]则说明这个条件可以满足

——————————————————————————————————————————————

但仍有一个例外：

假定我们以5为根节点（只画出了左子树嗷），设每一条边长为1

若k=4，那么4和1到5的距离加起来正好为4

但显然1到4这条链上不会有5，所以我们还要统计该点是从那个（根节点的亲儿子）来的

若两个点从同一个儿子过来的，那么就忽略这种情况

——————————————————————————————————————————————---

回到如何检验该询问能否成立

我们将所有的dis从小到大排一个序，设定两个坐标1和dis的长度分别为l,r

若dis[l]+dis[r]>k，就将r减一，这样总和就会变小

反之，将l加一，这样总和就会变大

情况2：

如果该条链不经过根节点，那么必然在他的子树里，我们就要进行分治

先将根节点断开，对于每一棵子树，我们先求得他的根节点也就是重心

之后我们仍然考虑两种情况：

1.经过根节点的路径

2.没经过根节点的路径

懂了吗，情况一就和上面一样，情况二则继续分治

从而有了这样一个divide函数：

void divide(int x) {
    vis[x]=1;
    calc(x);
    for(int i=head[x]; i; i=nxt[i]) {
        int y=to[i];
        if(vis[y]) continue;
        root=0;
        getrt(y,0,size[y]);
        divide(root);
    }
}

 

vis数组表示这个点已经被隔开来，calc函数用于解决在这个根节点上的情况一

之后对于他的每一个孩子，我们都要找到他的重心，然后继续搜索

下面贴一下calc函数，getrt函数，以及其附属函数

calc：

void calc(int x) {
    tot=1;
    a[tot]=x;
    dis[x]=0;
    father[x]=x;
    for(int i=head[x]; i; i=nxt[i]) {
        int y=to[i];
        if(vis[y]) continue;
        get(y,x,val[i],y);
    }
    sort(a+1,a+tot+1,cmp);
    for(int i=1; i<=m; i++) {
        int l=1,r=tot;
        if(ans[i]) continue;
        while(l<r) {
            if(dis[a[l]]+dis[a[r]]>query[i]) r--;
            else 
            if(dis[a[l]]+dis[a[r]]<query[i]) l++;
            else 
            if(father[a[l]]==father[a[r]])
            {
                if(dis[a[r]]==dis[a[r-1]])r--;
                else l++;
            }
            else {
                ans[i]=1;
                break;
            }
        }
    }
}

 dis[i]表示所有点到i的距离

father[i]表示i对应的根的亲儿子

 get函数用于得到所有的dis和father

之后就按照我们上面的思路，排序，查找，如果第i个询问可行，则ans[i]=1

然后是get函数以及cmp函数：

bool cmp(int x,int y) {return dis[x]<dis[y];}

void get(int x,int fa,int now,int rt) {
    tot++;
    a[tot]=x;
    dis[x]=now;
    father[x]=rt;
    for(int i=head[x]; i; i=nxt[i]) {
        int y=to[i];
        if(y==fa||vis[y]) continue;
        get(y,x,now+val[i],rt);
    }
}

 很明显，不用过多的分析。

然后是getrt函数

void getrt(int x,int fa,int total) {
    size[x]=1;
    maxsum[x]=0;
    for(int i=head[x]; i; i=nxt[i]) {
        int y=to[i];
        if(y==fa||vis[y]) continue;
        getrt(y,x,total);
        size[x]+=size[y];
        maxsum[x]=max(size[y],maxsum[x]);
    }
    maxsum[x]=max(maxsum[x],total-size[x]);
    if(!root||maxsum[x]<maxsum[root]) root=x;
}

依旧是很常规，maxsum[i]记录i的最大子树的大小，size记录他子节点以及他本身的个数

然后就完美的解决辽~

代码：

void add(int a,int b,int c) {
    cnt++;
    nxt[cnt]=head[a];
    to[cnt]=b;
    val[cnt]=c;
    head[a]=cnt;
}
void getrt(int x,int fa,int total) {
    size[x]=1;
    maxsum[x]=0;
    for(int i=head[x]; i; i=nxt[i]) {
        int y=to[i];
        if(y==fa||vis[y]) continue;
        getrt(y,x,total);
        size[x]+=size[y];
        maxsum[x]=max(size[y],maxsum[x]);
    }
    maxsum[x]=max(maxsum[x],total-size[x]);
    if(!root||maxsum[x]<maxsum[root]) root=x;
}
bool cmp(int x,int y) {
    return dis[x]<dis[y];
}
void get(int x,int fa,int now,int rt) {
    tot++;
    a[tot]=x;
    dis[x]=now;
    father[x]=rt;
    for(int i=head[x]; i; i=nxt[i]) {
        int y=to[i];
        if(y==fa||vis[y]) continue;
        get(y,x,now+val[i],rt);
    }
}
void calc(int x) {
    tot=1;
    a[tot]=x;
    dis[x]=0;
    father[x]=x;
    for(int i=head[x]; i; i=nxt[i]) {
        int y=to[i];
        if(vis[y]) continue;
        get(y,x,val[i],y);
    }
    sort(a+1,a+tot+1,cmp);
    for(int i=1; i<=m; i++) {
        int l=1,r=tot;
        if(ans[i]) continue;
        while(l<r) {
            if(dis[a[l]]+dis[a[r]]>query[i]) r--;
            else 
            if(dis[a[l]]+dis[a[r]]<query[i]) l++;
            else 
            if(father[a[l]]==father[a[r]])
            {
                if(dis[a[r]]==dis[a[r-1]])r--;
                else l++;
            }
            else {
                ans[i]=1;
                break;
            }
        }
    }
}
void divide(int x) {
    vis[x]=1;
    calc(x);
    for(int i=head[x]; i; i=nxt[i]) {
        int y=to[i];
        if(vis[y]) continue;
        root=0;
        getrt(y,0,size[y]);
        divide(root);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1; i<n; i++) {
        int x,y,w;
        cin>>x>>y>>w;
        add(x,y,w);
        add(y,x,w);
    }
    for(int i=1; i<=m; i++) {
        cin>>query[i];
        if(!query[i]) ans[i]=1;
    }
    maxsum[0]=n;
    getrt(1,0,n);
    divide(root);
    for(int i=1; i<=m; i++)
        if(ans[i]) cout<<"AYE"<<endl;
        else cout<<"NAY" <<endl;
    return 0;
}

View Code

query存储读入的k

ans用于记录该询问可不可行

在进入搜索前先找一遍重心

AC~