宝藏(树形DP)[SinGuLaRiTy] 树链问题,singularity问题。

lovebet 1 
lovebet 2

[SinGuLaRiTy] 树链问题,singularity问题

【SinGuLaRiTy-1035】 Copyright (c) SinGuLaRiTy 2017. All Rights
Reserved.

 

至于树链

树链是呀?这个新一关押似乎好陌生的词汇表达的莫过于就是以一如既往棵树被从一个节点到另外一个节点的门径。在群接近复杂的图论问题屡遭,我们其实要对那个进行适度的处理,把图转化为同一棵树,问题就会见得化简,再使用树链的有关思想便得比较轻松地解决。

立即道题目是颇考验思维的,n^2应该要比较好怀念的,主要是怎么样转移根之题材。转移根,在我看来应该是树形dp最为难之等同有些了,

树上倍增

所谓的“树及倍增”,其实就是千篇一律种植记录节点的方法。我们定义一个数组f[i][j],表示节点i的第2^j独祖先(通常认为节点i的父亲呢节点i的首先单祖先)。假设总共发生n个节点,我们十分易看到,对之数组中的i进行枚举的岁月复杂度为O(n),而针对性j进行枚举的日复杂度就如稍稍得差不多了,才O(logn)。

对于一个树形结构,我们可以于O(nlogn)的时刻外处理出f[][]数组:(与平常不同,由于递交推式只提到更粗之j,只待以外层枚举j,内层枚举i)

for(int i=1;i<=n;i++)
    f[i][0]=father[i];
for(int j=1;j<=LOG;j++)//这里的LOG表示常数log(n),通常取值为20左右
    for(int i=1;i<=n;i++)
        f[i][j]=f[f[i][j-1]][j-1];

以此代码应该要比较好掌握的:f[i][0]意味着的就是是节点i的第(2^0=1)个祖先,也即是i的大;节点i的第2^j独祖先为便是节点i的第2^(j-1)个祖先的第2^(j-1)个祖先,因为2^(j-1)+2^(j-1)=2^j。(好吧,可能产生接触绞,来画一个图)。

lovebet 3

这就是说,我们怎么行使f[][]数组快速稳定节点x的第k单祖先为?倍增数组要求一律次等只能前进跳2的平头不成幂个节点,我们得以因当下等同属性将k拆成一个亚前行制数,再经过2之次幂凑出k。代码如下:

int getk(int x,int k)
{
    for(int i=0;i<LOG;i++
        if(k&(1<<i))
            x=f[x][i];
    return x;
}

这就是说只要问题成为求x的深浅为d的先世为?(深度,若一个节点的第a独祖先为清节点,那么这个节点的深就吧a)
 其实为格外简短,只要稍微变换一下就算可成为上面的题目:

int getd(int x,int d)
{
    return getk(x,dep[x]-d);
}

貌似学会如何转移根,也就基本上考验通吃树形dp了。

不久前集体祖先问题(LCA)

哎呀是近日公共祖先?对于发出根树的随意两个节点u,v,u和v的共有祖先中深度最深(离根最远)的节点被称为u和v的近年公祖先。

那么怎么告少只节点的近年官祖先为?我们得经这简单个节点到干净节点的路径来判断。如下图,假而我们渴求节点4和节点5的近年公共祖先,我们发现它们到根本节点的门路分别吗4-3-2-1跟5-2-1,于是我们好打晚往前面还要对就半独途径进行遍历:它们的尾声一个路径点相同,倒数第二单路径点也一致,但是到倒数第三只就差了,于是我们管最后一组一致的节点作为最近公祖先——节点2就是是节点4和节点5之近年公共祖先。但是,这个历程有点复杂了:先要博两个节点到根本节点的路子再倒回来往回找,于是我们得以针对这过程进行优化。在算路径之前,我们事先同意这简单个节点的纵深:节点4的纵深为3,节点5之深度也2,于是我们管节点4朝着上转移到节点3,使个别单节点的深浅一致,转而求节点3跟节点5底近期国有祖先(这个操作必然不见面潜移默化结果)。这样一来,我们而对个别单节点进行路计算,他们之首先对准同一之路径点(依然是节点2)即为近年来公祖先。

lovebet 4

实质上,我们得一直用倍增数组查找最近集体祖先。(以下代码实际上求的是近来国有祖先之下的有数单节点,最近公祖先为father[u]和father[v])

for(i=LOG-1;i=0;i--)
    if(f[u][i]!=f[v][i])
        u=f[u][i], v=f[v][i];

当上这段代码之前,要对u和v进行特判:若u=v,那么是点自己就是是所求之近期公祖先;若u!=v,再进来代码求解。

 

一些模板题

洛谷 P3019 Meet Place 会见点 (USACO 2011 Mar-Silver)

Codevs 4605 LCA

COGS 1588 Distance Queries 距离咨询 (USACO 2004 Feb-Gold)

下面转一改观生佬链接:http://blog.csdn.net/FromATP/article/details/53200240

途径最值查询问题

 

【NOIP2013】货车运输

发 n 栋城,编号从 1 到 n,城市次来 m
条双向道路。每一样漫长道路对车子且发出份量限制,简称限重。现在发生 q
辆货车在运输货物,每部车起自己的起点城市跟终极都,司机等想清楚各个部车在未跳限重的图景下,最多克采用多更之商品。(可看n,m,q都是10万)

思路:请出图的绝充分生成树,
易知两触及在无限要命生成树上的门路最小値等价于本图备受之瓶子颈边的权値。记f[i][j]表示节点i的第2^j只祖先。另起一个数组g[i][j]表示节点i到第2^j单祖先最小值.。这有限只数组均经递推求得。在倍增法求LCA的历程中.同步记录路径最小值即可,也就是说,
每一样不成实行x=f[x][i]操作,同步记录ans=min(ans,g[x][i])。时间复杂度0((n+m)logn)。

<这书到处都发生,就不粘代码了>

题解

较好怀念的树形DP。。但是贯彻起来很多地方不是一般恶心。。。也许是ATP的方法太愚蠢了?总之好像这考的时节ATP最后半单小时想出去了而没码完只好写了50pts部分分=
=醉死了

那么就算先由50pts的开端说由吧。。可以想到是数额范围允许我们拿每个节点当做根每次都重复开展dfs,那即便因此一个f[i][0]表示从i号节点出发到它们的子树里去改变一缠绕最后还要回来的极度要命收益,f[i][1]意味着从今i号节点出发到它们的子树里改变一环最后不回的最好酷收益。那么分别坐每个点u为根dfs的时节最充分收益就是f[u][0]和f[u][1]的Max。

但100pts的说话肯定不克每次又dfs,就要考虑同百分之百dfs维护出具有需要之信。因为其使之是必定经过某一个触及的极度可怜收入路线,一全勤dfs的言语才会保障有从之点出发到它们的子树里活动相同环抱的无限特别收入,于是又维护一个g[i][0]数组代表从i这个点出到它们的子树外面走相同缠而回来的最深收益,g[i][1]表示从之点出来走相同围又回来的极其可怜收入。但是注意的情状是递推g数组的时因一旦分成在它父亲外面走相同缠与于其兄弟节点里活动相同围绕两种情景,所以搞它的兄弟节点的时候不能够连它自己。这个要小心。

那到底哪来维护这点儿单数组呢?对于f[i][0],反正它每次运动下还设回去,所以就算一个子树一个子树地考虑。对于目前子树v,f[v][0]凡是已经掌握的,那么跑至这子树里面走相同围再回去的进项就是得算出来。如果这收入大于0,显然选上v这个子树肯定会为解变得更出色。也就是说f[i][0]是名缰利锁维护的,枚举每一样株子树的下如果其的进项大于0就必要挑。

对于f[i][1],它要在i的有所子树中挑选同蔸子树,当跑至及时棵子树里面的当儿它便不再返回点i了。除了及时棵子树以外的外子树还是好用f[v][0]来贪心选择的。那么在递交推f[i][1]的时段每次枚举到一个子树v,显然目前底f[i][1]里头储存的结果对应之那么棵不回的子树在v前面。于是将分成仍然让v之前的那么棵子树不回去和让v不返两种植状况讨论。如果还让v之前的那么棵子树不回,v就要回来,于是便用f[v][0]贪地创新;否则因为v要回来,所以v之前有的且无能够返,就因故当下的f[i][0]加上f[v][1]来更新结果——这虽要求每次f[i][0]要在f[i][1]后更新否则f[i][0]里面存的就不是v之前的子树而有或连v了,就招致了重新更新。

g数组要求于到向下要无是自底向上递推,因为只有掌握了大人之状态才能够递推儿子。对于g[i][0],它是飞至外面转一圈又回到的太老收入,于是首先就承g[fa][0]的结果,表示她到其父亲节点的以外转了扳平缠绕又返回;然后还有它通过大及兄弟节点内转一圈回来的景,这个肯定不克枚举现算啊对吧,所以我们考虑采用之前的结果。注意到f[fa][0]尽管曾席卷了i的享有兄弟节点的信,但是问题虽在于有或吗还要概括了i,这是匪合法的。所以我们若判一下i有没有发出对f[fa][0]发生贡献,如果部分话使减小。因为是贪心选择的用呢不行好判断。

最后是g[i][1]。需要分成不回去的那么条路于它们父亲外面还是以它们兄弟节点内少局部讨论。如果不回的那漫长总长于大外面的语句虽是用g[fa][1]加上她到兄弟节点里改变一圈然后归的入账,这个跟上面g[i][0]计量的时光是相同的。关键就是是不返的那漫长总长更兄弟节点内的这种气象较辛苦。不可知一直用f[fa][1]何的来更新,因为在计算f[fa][1]的早晚所下的非回的很男或我即是时下要算的i。也就是用于递推i的好东西要确保它们不返的生男要以i外面。所以当递交推f数组的时段又循环了千篇一律全体,一开始递推f[u][1]的时刻记录了瞬间她不归的男是哪一个,然后还强制让这男肯定拐回来,递推一个f[u][2]。这样于递给推g[i][1]的时候,f[fa][1]和f[fa][2]肯定至少发生一个它们选择的匪回的门道是在i外面的,就用老来更新。更新的时刻还记得减去或许有的f[i][0]的贡献。

 

尽管如此大增长,但是挺详细,十分~\(≧▽≦)/~。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int n,p[300010],a[600010],nxt[600010],tot;
 6 long long f[300010][3],g[300010][2],val[300010],w[600010],rec[300010];
 7 void add(int x,int y,long long v){
 8     tot++;a[tot]=y;nxt[tot]=p[x];w[tot]=v;p[x]=tot;
 9 }
10 void dfs(int u,int fa){
11     int tmp=val[u],e;
12     f[u][0]=f[u][1]=f[u][2]=val[u];//0:back;1:not back
13     for (int i=p[u];i!=0;i=nxt[i])
14       if (a[i]!=fa){
15           int now,last;
16           dfs(a[i],u);
17           last=f[u][1]+max((long long)0,f[a[i]][0]-2*w[i]);
18           now=f[u][0]+max((long long)0,f[a[i]][1]-w[i]);
19           if (now>last){
20               f[u][1]=now;rec[u]=a[i];
21           }else f[u][1]=last;
22           if (f[a[i]][0]>=2*w[i]) f[u][0]+=f[a[i]][0]-2*w[i];
23       }
24     for (int i=p[u];i!=0;i=nxt[i])
25       if (a[i]!=fa&&a[i]!=rec[u]){
26           int now,last;
27           last=f[u][2]+max((long long)0,f[a[i]][0]-2*w[i]);
28           now=tmp+max((long long)0,f[a[i]][1]-w[i]);
29           f[u][2]=max(now,last);
30           if (f[a[i]][0]>=2*w[i]) tmp+=f[a[i]][0]-2*w[i];
31       }else if(a[i]==rec[u]) e=w[i];//记下最大值不回来节点的父边来更新
32     f[u][2]=max(f[u][2],f[u][2]+f[rec[u]][0]-2*e);//最后要判断一下
33 }
34 void dfs_again(int u,int fa,int edge){
35     int son;
36     g[u][0]=g[u][1]=0;
37     if (rec[fa]==u) son=f[fa][2];
38     else son=f[fa][1];//判断选择最大值还是次大值
39     son-=max(f[u][0]-2*edge,(long long)0);//减去当前子树的影响
40     g[u][1]=max(g[u][1],g[fa][0]+son-edge);//停在兄弟节点里的情况
41     if (f[u][0]>2*edge) son=f[u][0]-2*edge;
42     else son=0;//计算所有兄弟节点回来的价值和
43     son=f[fa][0]-son;//停在父亲外面的情况
44     g[u][1]=max(g[u][1],son+g[fa][1]-edge);
45     g[u][0]=max(g[u][0],son+g[fa][0]-2*edge);
46     for (int i=p[u];i!=0;i=nxt[i])
47       if (a[i]!=fa) dfs_again(a[i],u,w[i]);
48 }
49 int main()
50 {
51     freopen("treasure.in","r",stdin);
52     freopen("treasure.out","w",stdout);
53     scanf("%d",&n);
54     for (int i=1;i<n;i++){
55         int x,y,w;
56         scanf("%d%d%d",&x,&y,&w);
57         add(x,y,w);add(y,x,w);
58     }
59     for (int i=1;i<=n;i++) scanf("%d",&val[i]);
60     dfs(1,0);dfs_again(1,0,0);
61     for (int i=1;i<=n;i++)
62       printf("%I64d\n",max(f[i][0]+g[i][1],f[i][1]+g[i][0])); 
63     return 0;
64 }

巴了他的代码,我之代码在模拟赛中生出描绘到。

【CQBZOJ】避难向导   (2015年重庆多校NOIP模拟联考)

深受一定一棵n只节点的培养,点带权
m次询问,求从a走至b,遇到的第一个点权不低于w的节点的号子,不有输出-1
(n≤10w, m≤30w)

思路一:若c=LCA(a,b),我们拿一个路线拆解成a->c,
c->b两总理分.这样的裨益是各个一样片都是平等条祖先一苗裔的直链,,由于用求离a最近的点.所以原问题吃拆成了少数只分支任务:从一个沾交它们的某部祖先就条链上离这点以来/最远的权值不小于w的触发。记f[i][j]啊祖先数组,g[i][j]代表去节点i最近底2^j个祖先中极其特别的点权。显然可以通过二划分深度来成功这片只分支任务。复杂度0(m1og^2n)无法透过总体数额。

思路二:倘图,将同长达x-y的直链看成A和B两有:A中隐含2底整数不成幂个节点,且A的长逾x-y总长度的1/2;其余的片段也B。通过如此的笔触来观察上述两单分支任务:

一、离x最近的:

明白k时,可以O(1)判断答案是否在A中。 ①
如果当A中,枚举i从k-1到0即可得到答案。 ②
如果A中未存合法解,则叫x=f[x][k],递归进行以上过程。
对于①,整个递归过程遭到就出近水楼台先得月答案前见面吃执行同一涂鸦。
对于②,每次递归后k的值减少,而k上界为logn,下界为0,所以递归深度也O(logn)
综上。该操作复杂度为O(logn)。

二、离x最远的:


优先令x=f[x][k],递归在B段被求解。如递归返回后一度获答案,则一直回答案。

如经①没有获得答案,则O(1)检查A段受到是不是发生答案,如果没有,则x-y整段路径中无解。如果生,则枚举i从k-1到0即可定位答案。
类似子任务一样,该部分的复杂度为O(logn)。

lovebet 5

Code

lovebet 6#include<cstdio>
#include<algorithm> #include<cmath>
#include<cstdlib> #include<iostream>
#include<cstring> using namespace std; #define MAXN 100010
#define LOG 18 int
Log,n,m,l[MAXN],f[MAXN][2],ms[MAXN],t,a,b,c,x,y,qi,g[MAXN],s[MAXN],ans,fa[MAXN],p[MAXN][LOG],mx[MAXN][LOG];
void Read(int &x){ char c; while(c=getchar(),c!=EOF)
if(c>=’0’&&c<=’9′){ x=c-‘0′;
while(c=getchar(),c>=’0’&&c<=’9’) x=x*10+c-‘0’; ungetc(c,stdin);
return; } } struct node { int v,wt; node *next;
}edge[MAXN*2],*adj[MAXN],*ecnt=edge; void add(int u,int v,int wt)
{ node *p=++ecnt; p->v=v; p->wt=wt; p->next=adj[u];
adj[u]=p; } void dfs1(int u){ int v; for(node
*p=adj[u];p;p=p->next) { v=p->v; if(v==fa[u]) continue;
fa[v]=u; l[v]=l[u]+1; dfs1(v);
if(f[v][0]+p->wt>f[u][0]) { f[u][1]=f[u][0];
f[u][0]=f[v][0]+p->wt; ms[u]=v; } else
if(f[v][0]+p->wt>f[u][1])
f[u][1]=f[v][0]+p->wt; } } void dfs2(int u,int wt) {
if(ms[fa[u]]==u) g[u]=f[fa[u]][1]; else
g[u]=f[fa[u]][0]; g[u]=max(g[u],g[fa[u]])+wt; for(node
*p=adj[u];p;p=p->next) if(p->v!=fa[u])
dfs2(p->v,p->wt); } void prepare() { int i,j; for(i=1;i<=n;i++)
{ p[i][0]=fa[i]; mx[i][0]=s[fa[i]]; }
for(j=1;j<=Log;j++) for(i=1;i<=n;i++) {
p[i][j]=p[p[i][j-1]][j-1];
mx[i][j]=max(mx[i][j-1],mx[p[i][j-1]][j-1]); } } int
lca(int x,int y) { int i; if(l[x]<l[y]) swap(x,y);
for(i=Log;i>=0;i–) if(l[x]-(1<<i)>=l[y]) x=p[x][i];
if(x==y) return x; for(i=Log;i>=0;i–) if(p[x][i]!=p[y][i])
x=p[x][i],y=p[y][i]; return fa[x]; } int find1(int x,int d,int
a) { if(l[x]<=l[a]) return -1;
for(;l[p[x][d]]<l[a]&&d>=0;d–); if(mx[x][d]<qi)
return find1(p[x][d],d-1,a); for(int i=d-1;i>=0;i–)
if(mx[x][i]<qi) x=p[x][i]; return fa[x]; } int find2(int
x,int d,int a) { int i,ret; if(l[x]<=l[a]) return -1;
for(;l[p[x][d]]<l[a]&&d>=0;d–);
ret=find2(p[x][d],d-1,a); if(~ret) return ret;
if(mx[x][d]<qi) return -1; for(i=d-1;i>=0;i–)
if(mx[p[x][i]][i]>=qi) x=p[x][i]; return fa[x]; } int
main() { int i,u,v,wt; Read(n),Read(m),Read(a),Read(b),Read(c);
for(Log=0;1<<Log<=n;Log++); Log–; for(i=1;i<n;i++) {
Read(u),Read(v),Read(wt); add(u,v,wt); add(v,u,wt); } dfs1(1);
dfs2(1,0); for(i=1;i<=n;i++) s[i]=((long
long)max(f[i][0],g[i])+a)*b%c; prepare(); while(m–) {
Read(x),Read(y),Read(qi); int d,a=lca(x,y); ans=-1; if(s[x]>=qi)
ans=x; if(ans==-1) { for(d=0;1<<d<=l[x];d++); d–;
ans=find1(x,d,a); } if(ans==-1) { for(d=0;1<<d<=l[y];d++);
d–; ans=find2(y,d,a); } if(ans==-1&&s[y]>=qi) ans=y;
printf(“%d\n”,ans); } return 0; } View Code

轻重链剖分

当起来之前,我们用了解以下的术语:

重新男:对于一个父亲节点吧,其子树大小最深的小子。
重边(图被的粗边):连接父亲节点和重儿子的尽头。 轻边:重边以外的无尽。
重链:重边形成的链子。需要注意的是:没有连接重边的节点打成一长就含这个节点本身的重链(例如节点12)。

还有局部标志,我们会时不时提到:

siz[x]:节点x的子树大小,如siz[2]=5
son[x]:节点x的重儿子,如son[1]=4
top[x]:节点x所于重链顶端的节点,如top[11]=2, top[12]=12,
top[13]=1

lovebet 7

这就是说,如何用代码来落实轻重链剖分的历程吧?以下是伪代码:

void dfs1(u)
{
    siz[u]=1;
    for(v是u的儿子)
    {
        dfs1(v);
        siz[u]+=siz[v]; 
        if(siz[v]>siz[son[u]]) 
            son[u]=v;
    }
}
void dfs2(u)
{
    if(son[u])
        top[son[u]]=top[u],dfs2(son[u]);
    for(v是u的儿子且v!=son[u])
    {
        top[v]=v;
        dfs2(v);
    }
}
int main()
{
    dfsl(1),top[1]=1,dfs2(1);
}

另外,还要加某些属性:从任何一个节点一直于上动及干净,遇到的轻边为O(logn)级别(证明:轻边的两端点的子树点数之差至少也2倍增)。我们甚至可以发现:轻边数量之nlogn的常数级别实际上是特别小的。

通过,树链剖分就生了余应用:

告最近官祖先

定义dep[x]表示x的深度,如dep[1]=1, dep[7]=3。

int lca(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]>dep[top[v]])
            u=fa[top[u]];
        else
            v=fa[top[v]];
    }
    return dep[u]<dep[v] ? u:v;
}

假设v是u的祖宗,求既是u的祖先为是v的崽的点

int getlow(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(fa[top[u]]==v)
            return top[u];
        u=fa[top[u]];
    }
    return son[v];
}

恳请一个沾之先世中深为d的触及

据悉dfs2的代码实现,可以得出一致修重链上之持有点于dfs2的dfs序列中一定是连连的。记dfn[x]表示节点x是第几单给遍历到的节点;记id[x]意味着第x独遍历到的节点是谁。只待于dfs2函数体内部将报告句id[dfn[u]=++tmr]=u加在首先执行即可。

int find(int u,int d)
{
    while(dep[top[u]]>d)
        u=fa[top[u]];
    return id[dfn[u]-(dep[u]-d)];
}

有例题

HDU 5452 Minimum Cut (2015 ACM/ICPC 亚洲区沈阳站网络赛)

Codevs 4632 运输计划 (NOIP2015)

[补充] 另类桥边(割/割边)算法

割边的概念:对于一个不管往图,如果去丢其中之一一样漫漫边后一切图变成了分隔两个图,则该边称为割边。割边不在外环中。
以自由顺序保存边,然后开同样次并查集优化的生成树。所有割边一定在被其他一样蔸生成树中。
还同赖造访保存边的频繁组,忽略已经当生成树中的底限。对于其他有条边,它的出现一定会使生成树上产生一个围绕,这个环中的限显然还无是割边,于是将马上长长的路子的掩盖次数+1。
恳请出子树和,覆盖次数为0的边集就是割集。

片例题

BZOJ 3069 Hard Choice

BZOJ 4381 Odwiedziny

轻重链剖分小结

链剖实际运行速度非常急匆匆,可一直替代tarjan离线lca。

  空间复杂度 预处理复杂度 单次询问复杂度
倍增 O(nlogn) O(nlogn) O(logn)
链剖 O(n) O(n) O(nlogn)

 

 

 

其他一样接近题材:Kruskal树

(在关于Kruskal的座谈中,我们盖无比小生成树为例。)

我们且见面就此Kruskal算法来要最好小生成树:将限按权值排序,顺序加边,并为此连查集维护连通性。

脚,我们针对是算法进行多少之精益求精:将限视为额外的点,合并两单聚众时,将限对应之接触当新的祖辈,这样就算那个成了Kruskal树。它的高度最好深是O(n),但咱尚可以开展优化:我们发现,我们实际只是需要拜访它的绝望节点,因此,我们好用连查集的门路压缩进行优化。

lovebet 8

转变的Kruskal树有以下定理:

定理一:Kruskal树是同等棵二叉树(因为限一定就连接2独点),树被叶子节点也本的节点,其它节点是本来的限度。
定理二:在最小生成树的例证中,从叶子到干净之路线中,点权递增。
定理三:两只叶子节点的LCA的权值为原图中简单接触内的瓶颈边。

以是有些例题

BZOJ 3551 Peaks

Codevs 3287 货车运输 (NOIP2013)

再也来最终一个例题:过去的聚集

(原题找不顶了,只能写来约的题意)

发出n个点,初始时刻每个点单独为一个凑合。支持有限个操作:将点x和点y所在集合合并。查询第k涂鸦联合操作前,点a和点b是否以一个聚集中。
n≤1000000,强制在线

思路:

应用Kruskal树,边权设置为操作编号。由于本续加边的逐一边权依次递增,满足Kruskal算法的习性。
查询时,如果到目前为止两独点不同根,则答案肯定是no。
如果和根,则查询两只点之LCA的权值,若该权值小于k,则答案吧yes,否则也no。
两触及间瓶颈边为从a到b所必经的权值最酷之尽头,在主题中针对诺最后添加的无尽。

惋惜的凡,使用路径压缩实现的Kruskal树于布局完之前,是心有余而力不足支撑快查询LCA的。
如果支持离线操作,可以尽了所有联合操作之后还实施查询。
考虑动用Kruskal树的瓶颈是啊?
每一样不善合必须新建一个节点,导致树高无法控制。

当少数只节点内确立一个起权值的节点,等价于在及时点儿个节点内总是一条发出权值的限度。
给连查集的边赋上边权,表示这是第几软添加的度。
使用本秩合并优化,则养大可操纵在log级别。
两单节点在并查集中之途径最大值等于这片独节点的连结时间,也即是Kruskal树被LCA的权值。
并查集高度为O(logn),此时得以暴力求LCA。

至于该题中的连查集优化——按秩合并

免加优化地一直统一并查集,单次操作复杂度可能高达O(n)。当并查集的底限有边权时,路径压缩或会见损失边的消息。
概念并查集的秩,记rnk[x]代表以x为清之养之万丈(当x不是根时rnk[x]的价无意义都无见面给拜)。合并时,将高度重复怪之培养之彻底作为新的彻底。
以下也联合代码:

int find(int x)
{
    if(fa[x]==x)
        return x;
    return find(fa[x]);
}
void unite(int x,int y)
{
    x=find(x),y=find(y);
    if(rnk[x]>rnk[y])
        swap(x,y);
    fa[x]=y;
    if(rnk[x]==rnk[y])
        rnk[y]++;
}

好印证,按秩合并的连查集单次操作复杂度最深为O(logn)。
路径压缩的连查集单次操作的复杂度最特别为O(n),当操作的次数上O(n)级别时,均摊复杂度为O(logn)。

 

Time:2017-08-11

http://www.bkjia.com/cjjc/1222005.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1222005.htmlTechArticle\[SinGuLaRiTy\] 树链问题,singularity问题
【SinGuLaRiTy-1035】 Copyright (c) SinGuLaRiTy 2017. All Rights
Reserved. 关于培育链 树链是啊?这个新一拘留像大陌生…

相关文章