沈阳个人网站建设代理品牌,工信部备案,ftp怎么找网站后台,宁波网站建设优化技术文章目录前言树上启发式合并引入算法思想时间复杂度模板练习例题#xff1a;CF600E Lomsat gelralsolutioncodeCF208E Blood CousinssolutioncodeCF570D Tree RequestssolutioncodeCF1009F Dominant Indicessolutioncode前言
最近不是在⛏李超树嘛#xff0c;然后就去玩了下…
文章目录前言树上启发式合并引入算法思想时间复杂度模板练习例题CF600E Lomsat gelralsolutioncodeCF208E Blood CousinssolutioncodeCF570D Tree RequestssolutioncodeCF1009F Dominant Indicessolutioncode前言
最近不是在⛏李超树嘛然后就去玩了下线段树顺道碰见了线段树合并想起了线段树分治发现自己连点分治都不会于是多管齐下先把树上启发式合并⛏明白再说
树上启发式合并
引入
说到启发式合并我们最先想到的是什么 ————就是并查集
普通版
void makeSet( int n ) {for( int i 1;i n;i ) f[i] i;
}int find( int x ) {return ( f[x] x ) ? x : f[x] find( f[x] );
}void unionSet( int u, int v ) {int fu f[u], fv f[v];f[fv] fu;
}并查集按秩合并 对于两个大小不一样的集合将大小 小的并到大的 这个集合的大小可以认为是集合的高度在正常情况下 而我们将集合高度小的并到高度大的有助于我们找到父亲 让高度小的树成为高度较大的树的子树这个优化可以称为启发式合并算法
void makeSet( int n ) {for( int i 1;i n;i ) f[i] i, siz[i] 1;
}int find( int x ) {return ( f[x] x ) ? x : f[x] find( f[x] );
}void unionSet( int u, int v ) {int fu f[u], fv f[v];if( fu fv ) return;if( siz[fu] siz[fv] ) swap( fu, fv );f[fv] fu, siz[fu] siz[fv];
}而我们现在即将要见到的神秘加冰也是启发式合并的一类——树上启发式合并 树上启发式合并又叫dsuontreedsu\ on\ treedsu on tree
算法思想
首先发生地点是在树上 用一道例题将思想由抽象化为具象讲解 其他AC算法直接踹飞不考虑哈 人最原始的欲望就是性和杀戮 最暴力的算法就是直接硬刚对每一个点都暴力搞子树里面所有的点——O(n2)O(n^2)O(n2) 然后就可以成功TTT飞
我们考虑暴力算法的时间复杂度为什么会这么高究竟是卡在哪里了
树的遍历肯定是建立在dfsdfsdfs上的 你难不成搞bfs 看图 暴力的想法很简单——碰到一个点就暴算此点的答案 那么这个实现应该是从下往上计算的 当我们遍历到uuu的时候继续去弄son1son1son1 假设已经搞定了son1son1son1子树所有点接着就马不停蹄地去搞son2son2son2同理到son3son3son3 最后再来一遍uuu
发现某些节点啊总是加了删删了加 工具人石锤 因为uuu各个儿子之间是彼此独立的相互之间的答案是不造成干扰的 而这些加删操作时间复杂度就是该子树大小 这不上天谁上天非常恐怖兄嘚
那怎么办呢 暴力这个概念的存在就是为了和优化形成对应 在这个基础上树上启发式合并的思想就成功诞生了
算法思想
首先O(n)O(n)O(n)遍历一遍树求出每个点的重儿子——没错就是树链剖分的那个意思然后就可以开始搞答案了 2-1 先把uuu点所有子树的答案都计算完了再计算uuu——自下而上 2-2 轻儿子的所有贡献都要删掉——各自独立 2-3 重儿子的贡献不删掉 因此2-22-3决定了算法计算有一定的顺序先轻儿子再重儿子
看似只是换了个计算顺序只是有一个儿子没有暴力操作其它的跟暴力完全一样啊 但是这样就将时间复杂度变成了O(nlogn)O(nlogn)O(nlogn)
时间复杂度
像树链剖分一样定义轻边重边轻链重链轻儿子重儿子 红边表示重边黑边表示轻边黄点表示该点身份是父亲的重儿子 因为重儿子的sizesizesize一定≥\ge≥轻儿子的sizesizesize 所以父亲的sizesizesize一定≥\ge≥轻儿子sizesizesize的两倍 也就是说每往上一层新的父亲的sizesizesize至少是前一层的两倍 等价于可以说一个点到根节点的路径不会有超过lognlog\ nlog n条轻边
又因为树上启发式合并的操作重儿子的子树是不会有倒退操作的只有轻儿子的子树才会 所以一个点xxx被遍历操作的次数取决于他到根节点路径上的轻边数1 ps: 111是因为他本身要被遍历到
按最极限的最坏每个点被遍历的次数尽量多 情况考虑
一个节点的被遍历次数也大约只为logn1logn1logn1 总时间复杂度则为O(n(logn1))O(nlogn)O(n(logn1))O(nlogn)O(n(logn1))O(nlogn)
模板
还是意思意思给一个并没有什么卵用的模板吧
void dfs1( int u, int fa ) { //遍历整个树找每个点的重儿子siz[u] 1;for( int i 0;i G[u].size();i ) {int v G[u][i];if( v fa ) continue;dfs1( v, u );siz[u] siz[v];if( ! son[u] || siz[v] siz[son[u]] )son[u] v;}
}void modify( int u, int fa, bool flag ) {//flag0回退 flag1添加 if( flag ) {//搞一搞} else {//搞一搞}for( int i 0;i G[u].size();i )if( G[u][i] ! fa ) modify( G[u][i], u, flag );
}void dfs2( int u, int fa ) {for( int i 0;i G[u].size();i ) {int v G[u][i];if( v fa || v son[u] ) continue;dfs2( v, u );//先算轻儿子的答案modify( v, u, 0 );//计算完轻儿子的答案后 要把儿子的痕迹擦干净 为下一个儿子准备//...可能还有其他的操作}if( son[u] ) dfs2( son[u], u );//重儿子的贡献仍然保留 不回退for( int i 0;i G[u].size();i ) {int v G[u][i];if( v fa || v son[u] ) continue;else modify( v, u, 1 );//开始重新添加每个轻儿子的贡献 为后面计算自己准备}//...一堆操作
}有等价写法下面练习的代码基本上是用的这一种
void dfs1( int u, int fa ) {siz[u] 1;for( int i 0;i G[u].size();i ) {int v G[u][i];if( v fa ) continue;dfs1( v, u ), siz[u] siz[v];if( siz[v] siz[son[u]] || ! son[u] )son[u] v;}
}void modify( int u, int fa, int k ) {//操作一下for( int i 0;i G[u].size();i ) {int v G[u][i];if( v fa || vis[v] ) continue;modify( v, u, k );}
}void dfs2( int u, int fa, int type ) {for( int i 0;i G[u].size();i ) {int v G[u][i];if( v fa || v son[u] ) continue;dfs2( v, u, 0 );//此时先不着急}if( son[u] ) dfs2( son[u], u, 1 ), vis[son[u]] 1;modify( u, fa, 1 );//把所有轻儿子的贡献统计上//操作if( son[u] ) vis[son[u]] 0;if( ! type ) modify( u, fa, -1 );//在这里直接遍历整棵树开始回退 因此需要特别对重儿子打个标记
}练习 例题CF600E Lomsat gelral
…
solution
就是前面用来举例子的题比较板可能读题会有所误会 num[i]num[i]num[i]颜色iii出现的次数 cntcntcnt颜色出现最多的次数 ansansans颜色出现次数最多的所有颜色的和 然后直接搞就可以了具体可见代码
code
#include cstdio
#include vector
using namespace std;
#define maxn 100005
#define int long long
vector int G[maxn];
int n, cnt, ans;
int c[maxn], son[maxn], siz[maxn], num[maxn], result[maxn];void dfs1( int u, int fa ) {siz[u] 1;for( int i 0;i G[u].size();i ) {int v G[u][i];if( v fa ) continue;dfs1( v, u );siz[u] siz[v];if( ! son[u] || siz[v] siz[son[u]] )son[u] v;}
}void modify( int u, int fa, bool flag ) {//0回退 1添加 if( flag ) {num[c[u]] ;if( num[c[u]] cnt )cnt num[c[u]], ans c[u];else if( num[c[u]] cnt ) ans c[u];} elsenum[c[u]] --;for( int i 0;i G[u].size();i )if( G[u][i] ! fa ) modify( G[u][i], u, flag );
}void dfs2( int u, int fa ) {for( int i 0;i G[u].size();i ) {int v G[u][i];if( v fa || v son[u] ) continue;dfs2( v, u );modify( v, u, 0 );//计算完轻儿子的答案后 要把儿子的痕迹擦干净 cnt ans 0;}if( son[u] ) dfs2( son[u], u );//重儿子的贡献仍然保留 for( int i 0;i G[u].size();i ) {int v G[u][i];if( v fa || v son[u] ) continue;else modify( v, u, 1 );}num[c[u]] ;if( num[c[u]] cnt ) ans c[u], cnt num[c[u]];else if( num[c[u]] cnt ) ans c[u];result[u] ans;
}signed main() {scanf( %lld, n );for( int i 1;i n;i )scanf( %lld, c[i] );for( int i 1, u, v;i n;i ) {scanf( %lld %lld, u, v );G[u].push_back( v );G[v].push_back( u );}dfs1( 1, 0 );dfs2( 1, 0 );for( int i 1;i n;i )printf( %lld , result[i] );return 0;
}CF208E Blood Cousins
…
solution
可以考虑加一个假根000将森林变成一棵树 这个操作很常见 然后考虑转换一下题意uuu的kkk级祖先的儿子有多少个变成求同深度的uuu的兄弟伙个数
code
#include cstdio
#include vector
using namespace std;
#define ll long long
#define N 100005
vector int G[N];
vector pair int, int query[N];
int n, m;
bool vis[N];
int son[N], dep[N], Size[N];
ll cnt[N], ans[N];
int f[N][20];void dfs1( int u, int fa ) {Size[u] 1;dep[u] dep[fa] 1;f[u][0] fa;for( int i 1;i 20;i )f[u][i] f[f[u][i - 1]][i - 1];for( int i 0;i G[u].size();i ) {int v G[u][i];if( v fa ) continue;dfs1( v, u ), Size[u] Size[v];if( Size[v] Size[son[u]] || ! son[u] )son[u] v;}
}int kthF( int u, int k ) {for( int i 0;i 20;i )if( ( 1 i ) k ) u f[u][i];return u;
}void modify( int u, int fa, int k ) {cnt[dep[u]] k;for( int i 0;i G[u].size();i ) {int v G[u][i];if( v fa || vis[v] ) continue;modify( v, u, k );}
}void dfs2( int u, int fa, int type ) {for( int i 0;i G[u].size();i ) {int v G[u][i];if( v fa || v son[u] ) continue;dfs2( v, u, 0 );}if( son[u] ) dfs2( son[u], u, 1 ), vis[son[u]] 1;modify( u, fa, 1 );for( int i 0;i query[u].size();i )//-1是减去自己ans[query[u][i].second] cnt[query[u][i].first dep[u]] - 1;if( son[u] ) vis[son[u]] 0;if( ! type ) modify( u, fa, -1 );
}signed main() {scanf( %d, n );for( int i 1, x;i n;i ) {scanf( %d, x );G[i].push_back( x );G[x].push_back( i );}dfs1( 0, 0 );scanf( %d, m );for( int i 1, u, k;i m;i ) {scanf( %d %d, u, k );int Fa kthF( u, k );//找到自己的k级父亲 用lca跑if( ! Fa ) continue;query[Fa].push_back( make_pair( k, i ) );}dfs2( 0, 0, 0 );for( int i 1;i m;i ) printf( %lld , ans[i] );return 0;
}CF570D Tree Requests
…
solution
题目已经有所放水因为可以把字符打乱排序 所以肯定是≤1\le1≤1个字符出现了奇数次其它字符必须出现偶数次 对出现了奇数次的字符个数进行维护即可
code
#include cstdio
#include vector
using namespace std;
#define N 500005
vector int G[N];
vector pair int, int query[N];
int n, m;
int t[N], son[N], dep[N], num[N], tot[N], ans[N], Size[N];
bool vis[N];
int cnt[N][30];void dfs1( int u, int fa ) {Size[u] 1, dep[u] dep[fa] 1;for( int i 0;i G[u].size();i ) {int v G[u][i];if( v fa ) continue;dfs1( v, u );Size[u] Size[v];if( ! son[u] || Size[v] Size[son[u]] )son[u] v;}
}void modify( int u, int fa, int k ) {cnt[dep[u]][t[u]] k;num[dep[u]] k;if( cnt[dep[u]][t[u]] 1 ) tot[dep[u]] ;else tot[dep[u]] --;for( int i 0;i G[u].size();i )if( G[u][i] ! fa ! vis[G[u][i]] )modify( G[u][i], u, k );
}void dfs2( int u, int fa, bool flag ) {for( int i 0;i G[u].size();i )if( G[u][i] ! fa G[u][i] ! son[u] )dfs2( G[u][i], u, 0 );if( son[u] ) dfs2( son[u], u, 1 ), vis[son[u]] 1;modify( u, fa, 1 );for( int i 0;i query[u].size();i )ans[query[u][i].second] ( num[query[u][i].first] 0 || tot[query[u][i].first] 1 );if( son[u] ) vis[son[u]] 0;if( ! flag ) modify( u, fa, -1 );
}char s[N];int main() {scanf( %d %d, n, m );for( int i 2, x;i n;i ) {scanf( %d, x );G[x].push_back( i );G[i].push_back( x );}scanf( %s, s );for( int i 0;i n;i )t[i 1] s[i] - a;dfs1( 1, 0 );for( int i 1, x, y;i m;i ) {scanf( %d %d, x, y );query[x].push_back( make_pair( y, i ) );}dfs2( 1, 0, 1 );for( int i 1;i m;i )if( ans[i] ) printf( Yes\n );else printf( No\n );return 0;
}CF1009F Dominant Indices
…
solution
与例题的维护操作差不多这里用的是depdepdep深度差求kkk
code
#include cstdio
#include vector
using namespace std;
#define N 1000005
vector int G[N];
int n, Max;
int son[N], dep[N], Size[N];
int ans[N], cnt[N];
bool vis[N];void dfs1( int u, int fa ) {Size[u] 1, dep[u] dep[fa] 1;for( int i 0;i G[u].size();i ) {int v G[u][i];if( v fa ) continue;dfs1( v, u );Size[u] Size[v];if( ! son[u] || Size[v] Size[son[u]] )son[u] v;}
}void modify( int u, int fa, int k ) {cnt[dep[u]] k;if( cnt[dep[u]] cnt[Max] || ( cnt[dep[u]] cnt[Max] dep[u] Max ) )Max dep[u];for( int i 0;i G[u].size();i )if( G[u][i] ! fa ! vis[G[u][i]] )modify( G[u][i], u, k );
}void dfs2( int u, int fa, bool flag ) {for( int i 0;i G[u].size();i )if( G[u][i] ! fa G[u][i] ! son[u] )dfs2( G[u][i], u, 0 );if( son[u] ) dfs2( son[u], u, 1 ), vis[son[u]] 1;modify( u, fa, 1 );ans[u] Max - dep[u];if( son[u] ) vis[son[u]] 0;if( ! flag ) modify( u, fa, -1 );
}int main() {scanf( %d, n );for( int i 1, u, v;i n;i ) {scanf( %d %d, u, v );G[u].push_back( v );G[v].push_back( u );}dfs1( 1, 0 );dfs2( 1, 0, 1 );for( int i 1;i n;i )printf( %d\n, ans[i] );return 0;
}
