Codeforces 1467E. Distinctive Roots in a Tree（树上差分）

admin管理员组

文章数量:1622638

Codeforces Round #695 (Div. 2) 全文见：https://blog.csdn/qq_43461168/article/details/112598001

E. Distinctive Roots in a Tree

题意：输出符合条件的点的个数。条件：从这个点出发到任意一个点的路径中没有重复的值。

思路参考：https://blog.csdn/forever_shi/article/details/112467674

思路：反过来想。 题目要求符合条件的点的个数。 但是枚举每个点是否合法显然不合理。 但是判断一个点不合法比较简单。所以可以标记所有的不合法点。剩下的就是答案了。怎么标记呢。 假设当前点为pos，a[pos] 为 x 。考虑两种情况。

1. pos 的后代（某个子树中的某个节点） y == x。 那么除了 dfs序位于[pos - y] 之间的点。其他的点一定是不合法的。其他的点必然会经过这两个 x 的。显然不合法。所以要标记除这条路径上的所有点。 用到树上差分。利用dfs序可以很方便的找出 dfn[pos] - dfn[y] 的所有点。

2. 除了子树和自己以外。 还存在x，那么pos的所有子树都不合法。因为这说明，连接父亲的那条边过去，还会碰到一个x。那么如果以pos 的子节点为根。必然会经过pos 和 另一个x。 所以，同样用差分把pos所有子树打上标记。

还有一个小问题就是，数值比较大，可以开map计数。也可以离散化之后计数。 离散化比map快一些。

AC代码：

#include <iostream>
#include <bits/stdc++.h>
#define int long long
#define mk make_pair
#define gcd __gcd
using namespace std;
const double eps = 1e-10;
const int mod = 1e9+7;
const int N = 3e5+7;
int n,m,k,t = 1,cas = 1;
int a[N],b[N];
int cnt[N];     // 计数
int vis[N];     // 计数
int in[N];      // dfs 进入序号
int out[N];     // dfs 退出序号
int sum[N];     // 差分数组
vector<int> edge[N];
vector<int> values;
int tot = 0;

void dfs(int pos,int fa){
    in[pos] = ++tot;
    int cntt = vis[a[pos]] ++;
    for(int i = 0 ; i < edge[pos].size() ; i ++){
        int to = edge[pos][i];
        if(to == fa) continue;
        int now = vis[a[pos]];
        dfs(to,pos);
        if(vis[a[pos]] > now){
            sum[1] ++;
            sum[n+1] ++;
            sum[in[to]] --;
            sum[out[to]+1] ++;
        }
    }
    out[pos] = tot;
    if(vis[a[pos]] - cntt != cnt[a[pos]]){
        sum[in[pos]] ++;
        sum[out[pos]+1] --;
    }
}

signed main(){
    cin>>n;
    for(int i = 1 ; i <= n  ; i ++){
        cin>>a[i];
        values.push_back(a[i]);
    }
    for(int i = 0 ; i < n-1 ; i ++){
        int x,y;
        cin>>x>>y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    sort(values.begin(),values.end());
    values.erase(unique(values.begin(),values.end()),values.end());
    for(int i = 1 ; i <= n ; i ++){
        a[i] = lower_bound(values.begin(),values.end(),a[i])-values.begin();
        cnt[a[i]] ++;
    }
    dfs(1,-1);
    int ans = 0;
    for(int i = 1; i <= n ; i ++){
        sum[i] += sum[i-1];
        if(sum[i] == 0){
            ans ++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

本文标签： 树上差分codeforcesdistinctivetree