icontofig | 发布于 2019-09-04 15:41:58 | 阅读量 402 | LCA 树上差分
发布于 2019-09-04 15:41:58 | LCA 树上差分

题目大意

给定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(dep[y] < dep[x])swap(x,y);
    for(int i = 22;i >= 0;--i){
        if(dep[x] <= dep[f[y][i]]){
            y = f[y][i];
        }
    }
    if(x == y)return x;
    for(int i = 22;i >= 0;--i){
        if(f[y][i] != f[x][i]){
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}
int cnt = 0;
ll ff[maxn];
struct edge{
    int to,next;
}e[maxn<<1];
int h[maxn];
void add(int u,int v){
    e[cnt].to = v;e[cnt].next = h[u];h[u] = cnt++;
    e[cnt].to = u;e[cnt].next = h[v];h[v] = cnt++;
    return;
}
int k,u,v;
void dfs(int now,int fa,int depth){
    f[now][0] = fa;
    dep[now] = depth;
    for(int i = h[now];i != -1;i = e[i].next){
        int v = e[i].to;
        if(v == fa)continue;
        dfs(v,now,depth+1);
    }
    return;
}
ll quick_pow(ll x,ll b){
    ll ret = 1;
    while(b){
        if(b & 1){
            ret = (ret * x) % mod;
        }
        x = (x * x) % mod;
		b >>= 1;
    }
    return ret;
}
void init(){
    fac[1] = 1;
    for(ll i = 2;i < maxn;++i){
        fac[i] = fac[i-1] * i;
        fac[i] %= mod;
    }
    for(int i = 1;i < maxn;++i){
        ff[i] = quick_pow(fac[i],mod-2);
    }
    ff[0] = fac[0] = 1;
    return;
}
ll ck[maxn],cp[maxn];
void dfs2(int now,int fa){
    for(int i = h[now];i != -1;i = e[i].next){
        int v = e[i].to;
        if(v == fa)continue;
        dfs2(v,now);
        ck[now] += ck[v];
        cp[now] += cp[v];
    }
    return;
}
int main(){
    init();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--){
        cin >> n >> m >> k;
        for(int i = 0;i <= n;++i){
            ck[i] = cp[i] = 0;
        }
		cnt = 0;
		for(int i = 1;i <= n;++i)
			h[i] = -1;
        for(int i = 1;i < n;++i){
            cin >> u >> v;
            add(u,v);
        }
        dfs(1,0,1);
        dep[0] = 0;
        pre_lca();
        int pos;
        for(int i = 1;i <= m;++i){
            cin >> u >> v;
            pos = lca(u,v);
            ck[u]++;
            ck[v]++;
            ck[pos]--;
            ck[f[pos][0]]--;
            cp[u]++;
            cp[v]++;
            cp[pos] -= 2;
        }
        dfs2(1,0);
        ck[0] += ck[1];
        cp[0] += cp[1];
        ll ans = 0;
        for(int i = 1;i <= n;++i){
            if(ck[i] >= k){
                ans += ((fac[ck[i]] * ff[k]) % mod) * ff[ck[i] - k] % mod;
                ans %= mod;
            }
            if(cp[i] >= k){
                ans -= ((fac[cp[i]] * ff[k]) % mod) * ff[cp[i] - k] % mod;
                ans %= mod;
                ans += mod;
                ans %= mod;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}



内容更新于: 2019-09-04 15:42:25
链接地址: http://blog.leanote.com/post/icontofig/f0ab5b986137

上一篇: 2018 ACM/ICPC Asia Jiaozuo Regional K.Counting Failures on a Trie Trie 思维题 倍增 Hash

下一篇: 2019 南京网络赛 A.The beautiful values of the palace 思维题+扫描线+树状数组

402 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航