dsu on tree 本质上是一个 启发式合并 复杂度 \(O(n\log n)\) 不支持修改 只能支持子树统计 不能支持链上统计…
先跑一遍树剖的dfs1
搞出来轻重儿子…
求每个节点的子树上有多少颜色为k的节点
有一个朴素的\(N^2\)暴力做法…
每个点来个\(dfs\) 没了
好您会dfs序 主席树/莫队 您赢了？但是并没有dsu on tree 好打。。
每次加入 \(x\) 点的时候 考虑暴力将 \(x\) 的子树放入 然后取出 消除贡献…
所以先统计轻儿子 然后再统计重儿子 最后消除轻儿子的贡献…
树剖让这棵树变成\(\log n\) 条链…
所以易证复杂度 \(n \log n\)
// Isaunoya
#include<bits/stdc++.h>
using namespace std ;
using LL = long long ;
using uint = unsigned int ;
#define int long long
#define fir first
#define sec second
#define pb push_back
#define mp(x , y) make_pair(x , y)
template < typename T > inline void read(T & x) { x = 0 ; int f = 1 ; register char c = getchar() ;
for( ; ! isdigit(c) ; c = getchar()) if(c == '-') f = -1 ;
for( ; isdigit(c) ; c = getchar()) x = (x << 1) + (x << 3) + (c & 15) ;
x *= f ;
}
template < typename T > inline void print(T x) {
if(! x) { putchar('0') ; return ; }
static int st[105] ;
if(x < 0) putchar('-') , x = -x ;
int tp = 0 ;
while(x) st[++ tp] = x % 10 , x /= 10 ;
while(tp) putchar(st[tp --] + '0') ;
}
template < typename T > inline void print(T x , char c) { print(x) ; putchar(c) ; }
template < typename T , typename ...Args > inline void read(T & x , Args & ...args) { read(x) ; read(args...) ; }
template < typename T > inline void sort( vector < T > & v) { sort(v.begin() , v.end()) ; return ; }
template < typename T > inline void unique( vector < T > & v) { sort(v) ; v.erase(unique(v.begin() , v.end()) , v.end()) ; }
template < typename T > inline void cmax(T & x , T y) { if(x < y) x = y ; return ; }
template < typename T > inline void cmin(T & x , T y) { if(x > y) x = y ; return ; }
const int Mod = LLONG_MAX ;
inline int QP(int x , int y) { int ans = 1 ;
for( ; y ; y >>= 1 , x = (x * x) % Mod)
if(y & 1) ans = (ans * x) % Mod ;
return ans ;
}
template < typename T > inline T gcd(T x , T y) { if(y == 0) return x ; return gcd(y , x % y) ; }
template < typename T > inline T lcm(T x , T y) { return x * y / gcd(x , y) ; }
template < typename T > inline void mul(T & x , T y) { x = 1LL * x * y ; if(x >= Mod) x %= Mod ; }
template < typename T > inline void add(T & x , T y) { if((x += y) >= Mod) x -= Mod ; }
template < typename T > inline void sub(T & x , T y) { if((x -= y) < 0) x += Mod ; }
const int N = 1e5 + 10 ;
int n ;
int co[N] , head[N] , cnt = 0 ; int son[N] , size[N] ;
int ctl[N] , num[N] , top = 0 ; int a[N] , sum[N] ;
struct node { int v , nxt ; } e[N << 1] ;
inline void add(int u , int v) { e[++ cnt].v = v ; e[cnt].nxt = head[u] ; head[u] = cnt ; return ; }
inline void dfs(int u , int fa) {
size[u] = 1 ;
for(register int i = head[u] ; i ; i = e[i].nxt) {
int v = e[i].v ;
if(v == fa) continue ;
dfs(v , u) ;
size[u] += size[v] ;
if(size[v] > size[son[u]]) son[u] = v ;
}
}
inline void upd(int u , int fa , int val) {
sum[num[co[u]]] -= co[u] ;
num[co[u]] += val ;
sum[num[co[u]]] += co[u] ;
if(sum[top + 1]) ++ top ;
if(! sum[top]) -- top ;
for(register int i = head[u] ; i ; i = e[i].nxt) {
int v = e[i].v ;
if(v != fa && ! ctl[v]) upd(v , u , val) ;
}
}
inline void dfs2(int u , int fa , int kep) {
for(register int i = head[u] ; i ; i = e[i].nxt) {
int v = e[i].v ;
if(v ^ fa && v ^ son[u]) dfs2(v , u , 0) ;
} if(son[u]) dfs2(son[u] , u , 1) , ctl[son[u]] = 1 ;
upd(u , fa , 1) ;
ctl[son[u]] = 0 ;
a[u] = sum[top] ;
if(! kep) upd(u , fa , -1) ;
}
signed main() {
read(n) ;
for(register int i = 1 ; i <= n ; i ++) read(co[i]) ;
for(register int i = 1 ; i <= n - 1 ; i ++) {
int u , v ; read(u , v) ;
add(u , v) ; add(v , u) ;
} dfs(1 , 0) ; dfs2(1 , 0 , 1) ;
for(register int i = 1 ; i <= n ; i ++) print(a[i] , ' ') ;
return 0 ;
}
CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
这题要求重排之后回文 即可以用二进制表示
\(2^i\) 次刚好可以表示…
而组成回文串的要求是最多一个出现奇数次的字符…
#include<bits/stdc++.h>
using namespace std ;
int n ;
const int N = 5e5 + 10 ;
struct node {
int v , nxt , w ;
} e[N] ;
int head[N] , cnt = 0 ;
inline void add(int u , int v , int w) {
e[++ cnt] = { v , head[u] , w } ;
head[u] = cnt ; return ;
}
int sz[N] , son[N] ,d[N] , dep[N] ;
inline void dfs(int u) { sz[u] = 1 ;
for(register int i = head[u] ; i ; i = e[i].nxt) {
int v = e[i].v ;
d[v] = d[u] ^ (1 << e[i].w) ; dep[v] = dep[u] + 1 ;
dfs(v) ; sz[u] += sz[v] ;
if(sz[v] > sz[son[u]]) son[u] = v ;
}
}
int mx = 0 , col[1 << 22] , ans[N] , now = 0 ;
inline void calc(int u) {
if(col[d[u]]) { mx = max(mx , col[d[u]] - now + dep[u]) ; }
for(register int i = 0 ; i < 22 ; i ++)
if(col[(1 << i) ^ d[u]]) mx = max(mx , dep[u] + col[(1 << i) ^ d[u]] - now) ;
}
inline void Calc(int u) { calc(u) ;
for(register int i = head[u] ; i ; i = e[i].nxt) {
int v = e[i].v ; Calc(v) ;
}
}
inline void up(int u) { col[d[u]] = max(dep[u] , col[d[u]]) ; }
inline void upd(int u) { up(u) ;
for(register int i = head[u] ; i ; i = e[i].nxt) {
int v = e[i].v ; upd(v) ;
}
}
inline void clear(int u) { col[d[u]] = 0 ;
for(register int i = head[u] ; i ; i = e[i].nxt) {
int v = e[i].v ;
clear(v) ;
}
}
inline void dfs(int u , bool kep) {
for(register int i = head[u] ; i ; i = e[i].nxt) {
int v = e[i].v ;
if(v ^ son[u]) dfs(v , 0) ;
}
if(son[u]) dfs(son[u] , 1) ;
now = dep[u] << 1 ;
for(register int i = head[u] ; i ; i = e[i].nxt) {
int v = e[i].v ;
mx = max(mx , ans[v]) ;
}
for(register int i = head[u] ; i ; i = e[i].nxt) {
int v = e[i].v ;
if(v == son[u]) continue ;
Calc(v) ; upd(v) ;
}
calc(u); up(u) ; ans[u] = mx ;
if(! kep) { clear(u) ; mx = 0 ; }
}
signed main() {
#ifdef _WIN64
freopen("0.in" , "r" , stdin) ;
#endif
ios :: sync_with_stdio(false) ;
cin.tie(nullptr) ;
cout.tie(nullptr) ;
cin >> n ;
for(register int i = 2 ; i <= n ; i ++) {
int x ; char c ;
cin >> x >> c ;
add(x , i , (c - 'a')) ;
}
dfs(1) ; dfs(1 , 1) ;
for(register int i = 1 ; i <= n ; i ++)
cout << ans[i] << ' ' ;
return 0 ;
}