【生物】分类
这场比赛拿了个B题一血,舒服!
题意:模板题
给定一张连通图,求出以1为根的最小生成树(然后就跟图没啥关系了)。
对于这棵生成树,有3种操作+3中询问:
- 更换根节点
- 树上 x到 y的最短路径上的点权加 d
- 树上 x所在子树所有节点点权加 d
- 求 x和 y的 LCA
- 求 x到 y的最短路径上的点权之和
- 求 x所在子树所有节点点权之和
思路:关键在于换根以及求 lca
这个换根想了挺久都没有想法,实在没有正确复杂度的操作,真是太菜!
于是百度了一下,发现换根是种传统操作(板子),实际处理方法就是换根但不换树剖的信息!
(前置知识:树剖,并且树剖的同时记录 dfs序的 idleft和 idright)(以下所有“子树”是指在以1为根的树中)
- 换根
直接用一个 root记录当前根节点即可,就这么简单!当然这里方便了后面就会麻烦一些。 - 树上 x到 y的最短路径上的点权加 d
由于树上最短路径与根是哪个点无关,因此正常的做就好了。 - 树上 x所在子树所有节点点权加 d
考虑两种情况+一种特判:- 特判:若 x=root,那直接整棵树加 d
- root不在 x子树中,则显然根具体是哪个点不会影响这棵子树
- root在 x子树中,此时这棵子树会发生变化,真正的子树变成了属于以当前点向“上”的树,具体而言就是整棵树去掉原子树中 root所在的“树枝”后都是“ x所在的子树”。
然后问题就变成了如何找到这个“树枝”,我这里采用的倍增法,从 root倍增跳 father,跳到刚好是 x的直接儿子即可,复杂度 O(log2n)
- 求 x和 y的 LCA
这是本题难点,有不止一种方法,自认为我这方法挺不错(题解方法分类太多了),嘿嘿- 若 x和 y都属于原 root子树,则返回原 lca即可(很显然啦)
- 若一个属于,一个不属于,则 lca就是 root,因为它夹在中间了
- 若两个都不属于则分两种情况:
- 先考虑以二者的 lca为根的原子树是否包含 root,若不包含,则显然返回 lca即可
- 剩下的就是不包含的情况,我们将 x和 y分别用倍增跳 father,都跳到刚好使 root在当前原子树中即可,然后将最后的 x和 y取深度较大的(为了更接近 root)
- 求 x到 y的最短路径上的点权之和
同2,树上最短路径与根是哪个点无关 - 求 x所在子树所有节点点权之和
同3,考虑两种情况+一种特判即可。
Ok, all right! 此题不失为一道换根+树剖板子好题!复杂度目测为 O(nlog22n),集中在树剖+线段树区间操作处,已忽略一开始的MST复杂度。
代码
#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}
const int maxn = 3e5+7;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
struct Edge{
int u, v, w, id;
bool operator < (const Edge &rhs) const {
if(w==rhs.w) return id<rhs.id;
return w<rhs.w;
}
}e[maxn*2];
int n, m, r, root=1;
int a[maxn], belong[maxn];
int head[maxn], to[maxn*2], nxt[maxn*2], tot;
int lid[maxn], rid[maxn], rk[maxn], ID;
int son[maxn], top[maxn], sz[maxn], deep[maxn];
int fa[maxn], st[maxn][20];
int find(int a) { return a==belong[a]?a:belong[a]=find(belong[a]); }
inline void add_edge(int u, int v) {
++tot; to[tot]=v; nxt[tot]=head[u]; head[u]=tot;
++tot; to[tot]=u; nxt[tot]=head[v]; head[v]=tot;
}
void dfs0(int u, int f, int d) {
fa[u]=f; sz[u]=1; deep[u]=d;
for(int i=head[u]; i; i=nxt[i]) {
int v=to[i]; if(v==f) continue;
dfs0(v,u,d+1); sz[u]+=sz[v];
if(sz[v]>sz[son[u]]) son[u]=v;
}
}
void dfs(int u, int f, int t) {
rk[lid[u]=++ID]=u; top[u]=t;
if(son[u]) dfs(son[u],u,t);
for(int i=head[u]; i; i=nxt[i]) {
int v=to[i]; if(v==f||v==son[u]) continue;
dfs(v,u,v);
}
rid[u]=ID;
}
ll node[maxn<<2], lazy[maxn<<2];
void build(int l, int r, int now) {
if(l==r) {
node[now]=a[rk[l]];
return;
}
int m=(l+r)/2;
build(l,m,now<<1); build(m+1,r,now<<1|1);
node[now]=node[now<<1]+node[now<<1|1];
}
void push_down(int l, int r, int now) {
ll &d=lazy[now], m=(l+r)/2;
node[now<<1]+=ll(m-l+1)*d; lazy[now<<1]+=d;
node[now<<1|1]+=ll(r-m)*d; lazy[now<<1|1]+=d;
d=0;
}
void update(int x, int y, int d, int l, int r, int now) {
if(x>y) return;
if(x<=l&&r<=y) {
node[now]+=ll(r-l+1)*d;
lazy[now]+=d;
return;
}
if(lazy[now]) push_down(l,r,now);
int m=(l+r)/2;
if(x<=m) update(x,y,d,l,m,now<<1);
if(y>m) update(x,y,d,m+1,r,now<<1|1);
node[now]=node[now<<1]+node[now<<1|1];
}
ll query(int x, int y, int l, int r, int now) {
if(x>y) return 0;
if(x<=l&&r<=y) return node[now];
if(lazy[now]) push_down(l,r,now);
int m=(l+r)/2;
ll ans=0;
if(x<=m) ans+=query(x,y,l,m,now<<1);
if(y>m) ans+=query(x,y,m+1,r,now<<1|1);
return ans;
}
int lca(int x, int y) {
if(deep[x]<deep[y]) swap(x,y);
for(int i=19; i>=0; --i) if(deep[st[x][i]]>=deep[y]) x=st[x][i];
if(x==y) return x;
for(int i=19; i>=0; --i) if(st[x][i]!=st[y][i]) x=st[x][i], y=st[y][i];
return fa[x];
}
bool contain(int x, int r) {
return lid[r]<=lid[x]&&lid[x]<=rid[r];
}
void add_xyd(int x, int y, int d) {
while(top[x]!=top[y]) {
if(deep[top[x]]<deep[top[y]]) swap(x,y);
update(lid[top[x]],lid[x],d,1,n,1); x=fa[top[x]];
}
if(deep[x]<deep[y]) swap(x,y);
update(lid[y],lid[x],d,1,n,1);
}
void add_xd(int x, int d) {
if(root==x) update(1,n,d,1,n,1);
else if(!contain(root,x)) update(lid[x],rid[x],d,1,n,1);
else {
int r=root;
for(int i=19; i>=0; --i) if(deep[st[r][i]]>deep[x]) r=st[r][i];
update(1,lid[r]-1,d,1,n,1);
update(rid[r]+1,n,d,1,n,1);
}
}
int get_lca(int x, int y) {
int cas=contain(x,root)+contain(y,root);
if(cas==2) return lca(x,y);
if(cas==1) return root;
int LCA=lca(x,y);
if(!contain(root,LCA)) return LCA;
for(int i=19; i>=0; --i) {
if(st[x][i]&&!contain(root,st[x][i])) x=st[x][i];
if(st[y][i]&&!contain(root,st[y][i])) y=st[y][i];
}
if(!contain(root,x)) x=fa[x];
if(!contain(root,y)) y=fa[y];
return deep[x]>=deep[y]?x:y;
}
ll sum_xy(int x, int y) {
ll ans=0;
while(top[x]!=top[y]) {
if(deep[top[x]]<deep[top[y]]) swap(x,y);
ans+=query(lid[top[x]],lid[x],1,n,1); x=fa[top[x]];
}
if(deep[x]<deep[y]) swap(x,y);
ans+=query(lid[y],lid[x],1,n,1);
return ans;
}
ll sum_x(int x) {
if(root==x) return node[1];
if(!contain(root,x)) return query(lid[x],rid[x],1,n,1);
int r=root;
for(int i=19; i>=0; --i) if(deep[st[r][i]]>deep[x]) r=st[r][i];
return query(1,lid[r]-1,1,n,1)+query(rid[r]+1,n,1,n,1);
}
int main() {
//freopen("testin", "r", stdin);
//freopen("testout", "w", stdout);
n=read(), m=read(), r=read();
for(int i=1; i<=n; ++i) a[i]=read(), belong[i]=i;
for(int i=1; i<=r; ++i) {
int u=read(), v=read(), w=read();
e[i]=(Edge){u,v,w,i};
}
sort(e+1,e+1+r);
for(int i=1; i<=r; ++i) {
int x=find(e[i].u);
int y=find(e[i].v);
if(x!=y) belong[x]=y, add_edge(e[i].u,e[i].v);
}
dfs0(1,0,1);
dfs(1,0,1);
for(int j=0; j<=19; ++j) {
for(int i=1; i<=n; ++i)
if(!j) st[i][j]=fa[i];
else st[i][j]=st[st[i][j-1]][j-1];
}
build(1,n,1);
while(m--) {
int op=read();
if(op==1) root=read();
else if(op==2) {
int x=read(), y=read(), d=read();
add_xyd(x,y,d);
}
else if(op==3) {
int x=read(), d=read();
add_xd(x,d);
}
else if(op==4) {
int LCA=get_lca(read(),read());
printf("%lld\n", query(lid[LCA],lid[LCA],1,n,1));
}
else if(op==5) printf("%lld\n", sum_xy(read(),read()));
else if(op==6) printf("%lld\n", sum_x(read()));
}
}
出题人题解链接
他的 lca分类确实比我麻烦些。