网站建设 职责,网站分站加盟,北京理工大学网站开发与应用,如何把网站上传到空间树点涂色
luogu 3703
题目大意
给出一棵树#xff0c;每个节点的初始颜色不同#xff0c;做若干操作#xff1a; 1.在一个点到根节点路径上染上一种新的颜色 2.查询一条路径上有多少种不同的颜色 3.查询一个点x#xff0c;使该点到根节点路径的不同颜色种数最多
输入样…树点涂色
luogu 3703
题目大意
给出一棵树每个节点的初始颜色不同做若干操作 1.在一个点到根节点路径上染上一种新的颜色 2.查询一条路径上有多少种不同的颜色 3.查询一个点x使该点到根节点路径的不同颜色种数最多
输入样例
5 6
1 2
2 3
3 4
3 5
2 4 5
3 3
1 4
2 4 5
1 5
2 4 5输出样例
3
4
2
2数据范围
1⩽n,m⩽1051\leqslant n,m\leqslant 10^51⩽n,m⩽105
解题思路
对于该图可以建立LCT虚边连接的是不同颜色的点实边连接的是相同颜色的点然后对此进行操作 操作1和access操作相似 对于修改一个点x的颜色 对于修改链中的点本来x贡献为1修改后为0所以修改链深度大于y的p-1 而对于x原来所在链上的点本来x贡献为0修改后为1所以该链上深度大于y的p1 操作2相当于x点到lca的不同颜色种数加上y点到lca的不同颜色种数 就是pxpy−2×plca1p_xp_y-2\times p_{lca}1pxpy−2×plca1 操作3可以按dfs序建立线段树这样就可以查询子树内的最小值了
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 100010
using namespace std;
int n, m, x, y, z, w, tot, s[N2], fa[N], bg[N], ed[N], dep[N], lazy[N2], head[N], son[N][2], faa[N][20];
struct rec
{int to, next;
}a[N1];
void add(int x, int y)
{a[tot].to y;a[tot].next head[x];head[x] tot;return;
}
void downtate(int x)//线段树
{if (!lazy[x]) return;s[x * 2] lazy[x], lazy[x * 2] lazy[x];s[x * 2 1] lazy[x], lazy[x * 2 1] lazy[x];lazy[x] 0;return;
}
void up(int x)
{s[x] max(s[x * 2], s[x * 2 1]);return;
}
void change(int x, int L, int R, int l, int r, int y)
{if (L l R r){s[x] y;lazy[x] y;return;}downtate(x);int mid (L R) 1;if (r mid) change(x * 2, L, mid, l, r, y);else if (l mid) change(x * 2 1, mid 1, R, l, r, y);else change(x * 2, L, mid, l, mid, y), change(x * 2 1, mid 1, R, mid 1, r, y);up(x);return;
}
int ask(int x, int L, int R, int l, int r)
{if (L l R r) return s[x];int mid (L R) 1;downtate(x);if (r mid) return ask(x * 2, L, mid, l, r);else if (l mid) return ask(x * 2 1, mid 1, R, l, r);else return max(ask(x * 2, L, mid, l, mid), ask(x * 2 1, mid 1, R, mid 1, r));
}
bool NR(int x)//LCT
{return son[fa[x]][0] x || son[fa[x]][1] x;
}
bool IRS(int x)
{return son[fa[x]][1] x;
}
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;son[x][!k] y;son[y][k] g;fa[x] z;fa[y] x;return;
}
void Splay(int x)
{while(NR(x)){if (NR(fa[x])) rotate(IRS(x) IRS(fa[x]) ? fa[x] : x);rotate(x);}return;
}
int find_root(int x)
{while(son[x][0]) x son[x][0];return x;
}
void access(int x)
{for (int y 0; x; x fa[y x]){Splay(x);int z son[x][1];if (z) z find_root(z), change(1, 1, n, bg[z], ed[z], 1);//对原链上的点贡献1if (y) z find_root(y), change(1, 1, n, bg[z], ed[z], -1);//对修改的脸上的点贡献-1son[x][1] y;}return;
}
void dfs(int x)//求dfs序
{bg[x] w;dep[x] dep[fa[x]] 1;change(1, 1, n, bg[x], bg[x], dep[x]);for (int i 1; i 16; i)faa[x][i] faa[faa[x][i - 1]][i - 1];for (int i head[x]; i; i a[i].next)if (!bg[a[i].to]){faa[a[i].to][0] fa[a[i].to] x;dfs(a[i].to);}ed[x] w;
}
int lca(int x, int y)
{if (dep[x] dep[y]) swap(x, y);for (int i 16; i 0; --i)if (dep[faa[x][i]] dep[y]) x faa[x][i];for (int i 16; i 0; --i)if (faa[x][i] ! faa[y][i]) x faa[x][i], y faa[y][i];return x y ? x : faa[x][0];
}
int main()
{scanf(%d%d, n, m);for (int i 1; i n; i){scanf(%d%d, x, y);add(x, y);add(y, x);}dfs(1);while(m--){scanf(%d, x);if (x 1){scanf(%d, x);access(x);}else if (x 2){scanf(%d%d, x, y);z lca(x, y);x ask(1, 1, n, bg[x], bg[x]);y ask(1, 1, n, bg[y], bg[y]);z ask(1, 1, n, bg[z], bg[z]);printf(%d\n, x y - z * 2 1);}else{scanf(%d, x);printf(%d\n, ask(1, 1, n, bg[x], ed[x]));}}return 0;
}
