LCA 树上差分    发布于 2019-09-04   504人围观   0条评论

题目大意

给定n个点的树,其中有m条路径被标记,求问有多少种方案能够使得取k条被标记的路径并且所取的k条路径至少有一个共同点。

题解

 首先此题标记的是m条路径,也就是说,路径上所有点都是被标记的。

如果我们仅考虑对于一个点,选出k条路径都有这一个共同点的话,很容易想到方案书是C(vis,k),其中vis表示这个点被多少条路径标记。

那么我们的问题就成了如何去求每个点的vis值。

对于每一个路径,我们肯定不能通过暴力扫一遍去统计vis值,这样肯定是TLE的。

于是我们就有一个经典的思路:树上差分。

我们找路径起点u和终点v的lca,假设为pos,我们稍微思考一下,就可以知道,我们应该在u的位置+1,v的位置+1,然后在pos的位置-1,pos的父节点位置-1(保证pos也被访问一次而其上的节点不被访问)。

之后我们只需要在从根节点dfs一次,然后向上回溯的过程中更新所有的点的vis值就可以了。

但是还没完,如果我们把所有节点的方案都加在一起,势必会有重复的方案。

我们考虑重复的方案会是什么样的。

如果两个点相邻,那么他们重复的方案数即为C(vise,k),其中vise为两点之间的边。

所以我们只需要再减去所有共同边上的方案数就可以了。

vise的值的统计和前面vis的统计差不多,也是利用树上差分的思想,不过我们要用点的位置表示其父亲到其的边,然后对每条路径,在u的位置+1,v的位置+1,lca的位置-2。要注意和上面点的位置的统计的区别。

时间复杂度为O((n+m)logn + 2*n)

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 3e5+5;
int t;
ll fac[maxn];
int f[maxn][25];
int n,m;
void pre_lca(){
    for(int j = 1;j < 23;++j){
        for(int i = 1;i <= n;++i){
            f[i][j] = f[f[i][j-1]][j-1];
        }
    }
    return;
}
int dep[maxn];
int lca(int x,int y){
    if(d
查看更多