网站建设和连接器区公司名字,python基础语法,在线考试响应式网站模板下载,自动化的网站建设正题
题目链接:https://www.luogu.com.cn/problem/P3302 题目大意 nnn个点的一个森林#xff0c;要求支持以下操作
连接两个不连通的点询问两个点之间最短路径上第kkk大的数 解题思路
需要支持查询第kkk大#xff0c;是必定使用主席树的#xff0c;所以考虑如何合并两棵树…正题
题目链接:https://www.luogu.com.cn/problem/P3302 题目大意
nnn个点的一个森林要求支持以下操作
连接两个不连通的点询问两个点之间最短路径上第kkk大的数 解题思路
需要支持查询第kkk大是必定使用主席树的所以考虑如何合并两棵树可以更快。
考虑启发式合并每次将小的点合并到大的点上面那样每个点最多被合并logn\log nlogn次。也就是每次合并我们就将小的那颗树完全重构
考虑如何查询我们可以用主席树上储存根节点到该点的每个数的个数然后查询时我们可以用两个点到根节点的答案减去他们的lcalcalca处和lcalcalca的父节点处的答案即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N8e410,MN*600,K17;
struct node{ll to,next;
}a[N*2];
ll n,m,t,cnt,tot;
ll w[N],b[N],ls[N],rt[N];
ll root[N],siz[N],dep[N],f[N][K];
struct Seq_Tree{ll ls[M],rs[M],w[M],cnt;void Build(ll x,ll l,ll r){if(!x)xcnt;w[x]0;if(lr)return;ll mid(lr)1;Build(ls[x],l,mid);Build(rs[x],mid1,r);return;}ll Change(ll y,ll l,ll r,ll pos){ll xcnt,mid(lr)1;w[x]w[y]1;ls[x]ls[y];rs[x]rs[y];if(lr)return x;if(posmid)ls[x]Change(ls[y],l,mid,pos);else rs[x]Change(rs[y],mid1,r,pos);return x;}ll Ask(ll x,ll y,ll lca,ll fa,ll l,ll r,ll k){if(lr)return b[l];ll mid(lr)1,valw[ls[x]]w[ls[y]]-w[ls[lca]]-w[ls[fa]];if(valk)return Ask(ls[x],ls[y],ls[lca],ls[fa],l,mid,k);return Ask(rs[x],rs[y],rs[lca],rs[fa],mid1,r,k-val);}
}T;
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].tox;a[tot].nextls[y];ls[y]tot;return;
}
void dfs(ll x,ll fa){siz[root[x]];f[x][0]fa;dep[x]dep[fa]1;for(ll i1;iK;i)f[x][i]f[f[x][i-1]][i-1];rt[x]T.Change(rt[fa],1,cnt,w[x]);for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;root[y]root[x];dfs(y,x);}return;
}
void Connect(ll x,ll y){if(siz[root[x]]siz[root[y]])swap(x,y);root[y]root[x];dfs(y,x);addl(x,y);return;
}
ll LCA(ll x,ll y){if(dep[x]dep[y])swap(x,y);for(ll iK-1;i0;i--)if(dep[f[y][i]]dep[x])yf[y][i];if(xy)return x;for(ll iK-1;i0;i--)if(f[y][i]!f[x][i])xf[x][i],yf[y][i];return f[x][0];
}
int main()
{ll testcase;scanf(%lld,testcase);scanf(%lld%lld%lld,n,m,t);for(ll i1;in;i)scanf(%lld,w[i]),b[cnt]w[i];sort(b1,b1cnt);cntunique(b1,b1cnt)-b-1;for(ll i1;in;i)w[i]lower_bound(b1,b1cnt,w[i])-b;for(ll i1;im;i){ll x,y;scanf(%lld%lld,x,y);addl(x,y);}T.Build(rt[0],1,cnt);for(ll i1;in;i)if(!root[i]){root[i]i;dfs(i,0);}ll last0;for(ll i1;it;i){char op[4];ll x,y,k;scanf(%s,op);if(op[0]Q){scanf(%lld%lld%lld,x,y,k);x^last;y^last;k^last;ll lcaLCA(x,y);lastT.Ask(rt[x],rt[y],rt[lca],rt[f[lca][0]],1,cnt,k);printf(%lld\n,last);}else{scanf(%lld%lld,x,y);x^last;y^last;Connect(x,y);}}return 0;
}
