dsu on tree简介及例题

$dsuontree$
树上启发式合并，多用于对子树的暴力询问，通过使用轻重链定义来进行优化，将算法复杂度降到$O(nlogn)$
算是一种优雅的暴力

一棵树n个点，每个点有一个颜色 要求每个结点子树的出现哪个颜色次数最多 如果有多个颜色次数同时最多，结果为这些颜色编号相加

原理

引入一个结论：从某一个点到根的路径中轻链的个数不会超过$logn$

证明：
从一个结点开始往上到根的过程中，每次交汇到一个点，如果这个点是轻链，那么这个点的子节点数一定比重链的少，假设这个轻链对应子树结点大小为$y$,这个交汇点子树结点大小为$x$，那么$y<x/2$
如果这个点到根上有z个轻链，那么需要交汇z次
那么这个点的子树结点个数会成为$num<=\frac{n}{2^z}$
$num>=1$，所以$z<logn$

并且，由于递归的性质，每次在递归return之后会回到一个父亲，那么在返回的时候，我们之前算的子树完全可以保留一个回到父亲节省下次计算，那么，我们每次最后访问重儿子，并且把重儿子的贡献保留传递给父亲继续计算，然后把轻儿子暴力计算，通过这个结论我们可以发现这样的复杂度最后只会达到$O(nlogn)$

算法

可以简化为如下的模版：

int sz[N], son[N]; vector<int> g[N]; void dfs(int u, int fa) { 
         sz[u] = 1; for (auto v : g[u]) { 
         if (v == fa) continue; dfs(v, u); sz[u] += sz[v]; if (sz[v] > sz[son[u]]) son[u] = v; } } int Son; //add函数为计算贡献的方法 void add(int u, int fa, int val) { 
         } 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), Son = son[u]; add(u, fa, 1) Son = 0; if (!op) add(u, fa, -1); } 

这样就形成了一个模版

例题

1. Lomsat gelral（引题）

/* Author : zzugzx Lang : C++ Blog : blog.csdn.net/_ */ #include 
           using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define endl '\n' #define SZ(x) (int)x.size() #define mem(a, b) memset(a, b, sizeof(a)) typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; //const int mod = 1e9 + 7; const int mod = ; const double eps = 1e-8; const double pi = acos(-1.0); const int maxn = 1e6 + 10; const int N = 1e2 + 10; const ll inf = 0x3f3f3f3f; const ll oo = 8e18; const int dir[][2]={ 
         { 
         0, 1}, { 
         1, 0}, { 
         0, -1}, { 
         -1, 0}, { 
         1, 1}, { 
         1, -1}, { 
         -1, 1}, { 
         -1, -1}}; int col[maxn], sz[maxn], son[maxn]; vector<int> g[maxn]; void dfs(int u, int fa) { 
          sz[u] = 1; for (auto v : g[u]) { 
          if (v == fa) continue; dfs(v, u); sz[u] += sz[v]; if (sz[v] > sz[son[u]]) son[u] = v; } } ll ans[maxn], sum, cnt[maxn], Son, mx; void add(int u, int fa, int val) { 
          cnt[col[u]] += val; if (cnt[col[u]] > mx) { 
          mx = cnt[col[u]]; sum = col[u]; } else if (cnt[col[u]] == mx) { 
          sum += col[u]; } for (auto v : g[u]) { 
          if (v == fa || v == Son) continue; add(v, u, val); } } 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), Son = son[u]; add(u, fa, 1); Son = 0; ans[u] = sum; if (!op) add(u, fa, -1), sum = 0, mx = 0; } int main() { 
          ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); int n; cin >> n; for (int i = 1; i <= n; i++) cin >> col[i]; for (int i = 1; i < n; i++) { 
          int u, v; cin >> u >> v; g[u].pb(v); g[v].pb(u); } dfs(1, 0); dfs1(1, 0, 0); for (int i = 1; i <= n; i++) cout << ans[i] << ' '; return 0; } 

2.Tree Requests

/* Author : zzugzx Lang : C++ Blog : blog.csdn.net/_ */ #include 
           using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define endl '\n' #define SZ(x) (int)x.size() #define mem(a, b) memset(a, b, sizeof(a)) typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; //const int mod = 1e9 + 7; const int mod = ; const double eps = 1e-8; const double pi = acos(-1.0); const int maxn = 5e5 + 10; const int N = 1e2 + 10; const ll inf = 0x3f3f3f3f; const ll oo = 8e18; const int dir[][2]={ 
         { 
         0, 1}, { 
         1, 0}, { 
         0, -1}, { 
         -1, 0}, { 
         1, 1}, { 
         1, -1}, { 
         -1, 1}, { 
         -1, -1}}; char c[maxn]; int sz[maxn], son[maxn], dep[maxn]; vector<int> g[maxn]; vector<pii> qry[maxn]; void dfs(int u, int fa) { 
          sz[u] = 1, dep[u] = dep[fa] + 1; for (auto v : g[u]) { 
          if (v == fa) continue; dfs(v, u); sz[u] += sz[v]; if (sz[v] > sz[son[u]]) son[u] = v; } } bool ans[maxn]; int cnt[maxn][26], Son; void add(int u, int fa, int val) { 
          cnt[dep[u]][c[u] - 'a'] += val; for (auto v : g[u]) { 
          if (v == fa || v == Son) continue; add(v, u, val); } } bool check(int x) { 
          int res = 0; for (int i = 0; i < 26; i++) if (cnt[x][i] & 1) res++; return res <= 1; } 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), Son = son[u]; add(u, fa, 1); Son = 0; for (auto i : qry[u]) { 
          int id = i.se, d = i.fi; if (check(d)) ans[id] = 1; else ans[id] = 0; } if (!op) add(u, fa, -1); } int main() { 
          ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); int n, _; cin >> n >> _; for (int i = 2; i <= n; i++) { 
          int x; cin >> x; g[x].pb(i); g[i].pb(x); } for (int i = 1; i <= n; i++) cin >> c[i]; for (int i = 1; i <= _; i++) { 
          int v, h; cin >> v >> h; qry[v].pb({ 
         h, i}); } dfs(1, 0); dfs1(1, 0, 0); for (int i = 1; i <= _; i++) if (ans[i]) cout << "Yes" << endl; else cout << "No" << endl; return 0; } 

3.Strange Memory

/* Author : zzugzx Lang : C++ Blog : blog.csdn.net/_ */ #include 
           using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define endl '\n' #define SZ(x) (int)x.size() #define mem(a, b) memset(a, b, sizeof(a)) typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; //const int mod = 1e9 + 7; const int mod = ; const double eps = 1e-8; const double pi = acos(-1.0); const int maxn = 1e6 + 10; const int N = 1e5 + 10; const ll inf = 0x3f3f3f3f; const ll oo = 8e18; const int dir[][2]={ 
         { 
         0, 1}, { 
         1, 0}, { 
         0, -1}, { 
         -1, 0}, { 
         1, 1}, { 
         1, -1}, { 
         -1, 1}, { 
         -1, -1}}; int sz[N], son[N], a[N]; vector<int> g[N]; void dfs(int u, int fa) { 
          sz[u] = 1; for (auto v : g[u]) { 
          if (v == fa) continue; dfs(v, u); sz[u] += sz[v]; if (sz[v] > sz[son[u]]) son[u] = v; } } ll ans; int cnt[][18][2], Son; void calc(int u, int fa, int w) { 
          for (int i = 0; i < 18; i++) ans += (1ll << i) * cnt[a[u] ^ w][i][!((u >> i) & 1)]; for (auto v : g[u]) { 
          if (v == fa || v == Son) continue; calc(v, u, w); } } void add(int u, int fa, int val) { 
          for (int i = 0; i < 18; i++) cnt[a[u]][i][(u >> i) & 1] += val; for (auto v : g[u]) { 
          if (v == fa || v == Son) continue; add(v, u, val); } } 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), Son = son[u]; for (auto v : g[u]) { 
          if (v == fa || v == Son) continue; calc(v, u, a[u]); add(v, u, 1); } for (int i = 0; i < 18; i++) cnt[a[u]][i][(u >> i) & 1] += 1; Son = 0; if (!op) add(u, fa, -1); } int main() { 
          ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i < n; i++) { 
          int u, v; cin >> u >> v; g[u].pb(v); g[v].pb(u); } dfs(1, 0); dfs1(1, 0, 0); cout << ans << endl; return 0; }