兰山区网站建设推广,家装公司是做什么的,移动公司网络维护,做公司网站需要什么材料正题
luogu CF1137F 题目大意
定义一棵树的产出序列为依次删除权值最小的叶子节点的顺序 进行q此操作#xff1a; 1.把一个点的权值改为当前树中的最大权值1 2.查询一个点在删除序列中的位置 3.给出两个点#xff0c;查询哪个在删除序列中的位置更前 解题思路
假设已经求出…正题
luogu CF1137F 题目大意
定义一棵树的产出序列为依次删除权值最小的叶子节点的顺序 进行q此操作 1.把一个点的权值改为当前树中的最大权值1 2.查询一个点在删除序列中的位置 3.给出两个点查询哪个在删除序列中的位置更前 解题思路
假设已经求出了删除序列且最大权值的点为y那么修改一个点x相当于把x~y上的点放到序列后面对于其它点必然不是在x或y删除后再删除的
这就是要提取出一条树链可以使用LCT
以权值最大的点为根节点一个点往上若干个权值比它小的点为一条链因为这些点要会当前点删除后依次删除当前点删除了那么其它叶子结点一定都大于当前点也就大于链上其它点
给这条链上的所有点的颜色染上链上最深点的权值
那么查询就相当于查找颜色比当它小的点的个数加上链上比它深的点的个数
修改就相当于连接x~y的链换根染色
对于查找颜色比它小的点用树状数组即可 代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 200021
using namespace std;
int n, q, x, y, w, tot, cl[N], head[N];
string str;
struct rec
{int to, next;
}a[N1];
struct tree//树状数组
{int n, c[N1];void change(int x, int y){for (; x n; x x-x)c[x] y;return;}int ask(int x){int sum 0;for (; x; x - x-x)sum c[x];return sum;}
}t;
struct LCT
{int p[N], fa[N], sz[N], son[N][2];bool NR(int x){return fa[x] (son[fa[x]][0] x || son[fa[x]][1] x);}bool IRS(int x){return son[fa[x]][1] x;}void push_up(int x){sz[x] sz[son[x][0]] sz[son[x][1]] 1;return;}void pushr(int x){p[x] ^ 1;swap(son[x][0], son[x][1]);return;}void push_down(int x){if (son[x][0]) cl[son[x][0]] cl[x];//颜色if (son[x][1]) cl[son[x][1]] cl[x];if (p[x]){if (son[x][0]) pushr(son[x][0]);if (son[x][1]) pushr(son[x][1]);p[x] 0;}return;}void push_hall(int x){if (NR(x)) push_hall(fa[x]);push_down(x);return;}void rotate(int x){int y fa[x], z fa[y], k IRS(x), g son[x][!k];if (NR(y)) son[z][IRS(y)] x;if (g) fa[g] y;fa[x] z;fa[y] x;son[x][!k] y;son[y][k] g;push_up(y);return;}void Splay(int x){push_hall(x);while(NR(x)){if (NR(fa[x])) rotate(IRS(x) IRS(fa[x]) ? fa[x] : x);rotate(x);}push_up(x);}void access(int x){for (int y 0; x; x fa[y x]){Splay(x);son[x][1] 0;push_up(x);t.change(cl[x], -sz[x]);//减去原来的颜色t.change(w, sz[x]);//改成现在的颜色son[x][1] y;push_up(x);}return;}void make_root(int x){w;access(x);Splay(x);cl[x] w;//染色pushr(x);return;}int ask(int x){Splay(x);return sz[son[x][1]] 1 t.ask(cl[x] - 1);}
}T;
void add(int x, int y)
{a[tot].to y;a[tot].next head[x];head[x] tot;return;
}
void dfs(int x)
{cl[x] x;for (int i head[x]; i; i a[i].next)if (!cl[a[i].to]){T.fa[a[i].to] x;dfs(a[i].to);if (cl[a[i].to] cl[x]){cl[x] cl[a[i].to];T.son[x][1] a[i].to;}}t.change(cl[x], 1);T.push_up(x);return;
}
int main()
{scanf(%d%d, n, q);for (int i 1; i n; i){scanf(%d%d, x, y);add(x, y);add(y, x);}t.n n q;w n;dfs(n);//连初始的图while(q--){cinstr;if (str up){scanf(%d, x);T.make_root(x);}else if (str when){scanf(%d, x);printf(%d\n, T.ask(x));}else{scanf(%d%d, x, y);printf(%d\n, T.ask(x) T.ask(y) ? x : y);}}return 0;
}
