这个算法是这个人发明的 DSU On tree

介绍

算法流程大致是这样:

  1. 先递归计算轻儿子子树,递归结束时消除他们的贡献
  2. 再递归计算重儿子子树,保留他的贡献
  3. 再计算当前子树中所有轻子树的贡献
  4. 更新当前子树的答案
  5. 如果当前子树是父节点的轻子树,消除当前子树的贡献

复杂度

复杂度分析

显然只有遇到轻边才会把自己的信息合并到父节点
树链剖分后每个点到根的路径上有$logn$
条轻边和$logn$条重链
一个点的信息只会向上合并$logn$次
如果一个点的信息修改是$O(1)$的,那么总复杂度就是$O(nlogn)$

题目

Codeforce 600E

这题就是模板题啦

#include<bits/stdc++.h>

#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define lowbit( x ) (x&(-x))
#define SZ( v ) ((int)(v).size())
#define All( v ) (v).begin(), (v).end()
#define mp( x , y ) make_pair(x,y)
using namespace std;
typedef long long ll;
typedef pair < int , int > P;
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
vector < int > G[N];
int n , a[N] , sz[N] , son[N] , cnt[N] ;
int mx ;
ll sum , ans[N];

void dfs ( int u , int fa ) {
    sz[u] = 1;
    for ( auto &v:G[u] ) {
        if ( v != fa ) {
            dfs ( v , u );
            sz[u] += sz[v];
            if ( ! son[u] || ( sz[v] > sz[son[u]] ) )
                son[u] = v;
        }
    }
}

void add ( int u , int fa , int val , int Son ) {
    cnt[a[u]] += val;
    if ( cnt[a[u]] > mx ) {
        mx = cnt[a[u]];
        sum = a[u];
    } else if ( cnt[a[u]] == mx ) sum += a[u];
    for ( auto &v:G[u] ) {
        if ( v != fa && v != Son ) add ( v , u , val , Son );
    }
}

void dfs1 ( int u , int fa , int op ) {
    for ( auto &v:G[u] ) {
        if ( v == fa || v == son[u] ) continue;
        dfs1 ( v , u , 0 );
    }
    if ( son[u] ) dfs1 ( son[u] , u , 1 );
    add ( u , fa , 1 , son[u] );
    ans[u] = sum;
    if ( ! op ) {
        add ( u , fa , - 1 , 0 );
        sum = 0;
        mx = 0;
    }
}

int main () {
    scanf ( "%d" , &n );
    for ( int i = 1 ; i <= n ; ++ i ) scanf ( "%d" , &a[i] );
    int u , v;
    for ( int i = 1 ; i < n ; ++ i ) {
        scanf ( "%d%d" , &u , &v );
        G[u].push_back ( v );
        G[v].push_back ( u );
    }
    dfs ( 1 , - 1 );
    dfs1 ( 1 , - 1 , 0 );
    for ( int i = 1 ; i <= n ; ++ i ) printf ( "%lld " , ans[i] );
    puts ( "" );
    return 0;
}

Codeforce 570D

#include<bits/stdc++.h>
 
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define lowbit( x ) (x&(-x))
#define SZ( v ) ((int)(v).size())
#define All( v ) (v).begin(), (v).end()
#define mp( x , y ) make_pair(x,y)
using namespace std;
typedef long long ll;
typedef pair < int , int > P;
const int N = 5e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
vector < int > G[N];
int n , m , a[N] , sz[N] , son[N] , cnt[N];
int odd , ans[N] , h[N] , dep[N];
bool vis[N][30];
char s[N];
vector < P > Q[N];
 
void dfs ( int u ) {
    sz[u] = 1;
    for ( auto &v:G[u] ) {
        dep[v] = dep[u] + 1;
        dfs ( v  );
        sz[u] += sz[v];
        if ( ! son[u] || ( sz[v] > sz[son[u]] ) )
            son[u] = v;
    }
}
 
void add ( int u ,  int Son ) {
    vis[dep[u]][s[u] - 'a'] ^= 1;
    if ( vis[dep[u]][s[u] - 'a'] ) cnt[dep[u]] ++;
    else cnt[dep[u]] --;
    for ( auto &v:G[u] ) {
        if ( v != Son ) add ( v , Son );
    }
}
 
void dfs1 ( int u , int op ) {
    for ( auto &v:G[u] ) {
        if ( v == son[u] ) continue;
        dfs1 ( v , 0 );
    }
    if ( son[u] ) dfs1 ( son[u] ,1 );
    add ( u ,  son[u] );
    for ( auto &q:Q[u] ) {
        ans[q.second] = ( cnt[q.first] <= 1 );
    }
    if ( ! op) {
        add ( u ,  0 );
        odd = 0;
    }
}
 
int main () {
    scanf ( "%d%d" , &n , &m );
    int u , v , h;
    dep[1] = 1;
    for ( int i = 2 ; i <= n ; ++ i ) {
        scanf ( "%d" , &u );
        G[u].push_back ( i );
    }
    scanf ( "%s" , s + 1 );
    for ( int i = 1 ; i <= m ; ++ i ) {
        scanf ( "%d%d" , &v , &h );
        Q[v].push_back ( mp( h , i ) );
    }
    dfs ( 1 );
    dfs1 ( 1 , 0 );
    for ( int i = 1 ; i <= m ; ++ i )
        puts ( ans[i] ? "Yes" : "No" );
    puts ( "" );
    return 0;
}
Last modification:March 19th, 2020 at 11:32 pm
如果觉得我的文章对你有用,请随意赞赏