codeforces 600E E. Lomsat gelral
传送门: https://codeforces.com/contest/600/problem/E
题意:
给你一颗 n 个节点的树, 树上的每一个节点都有一种颜色, 询问每一个节点所在的子树颜色数量最多的那些颜色的值的总和
题解:
维护子树颜色的数量和答案, 线段树合并即可
代码:
- /**
- * ┏┓ ┏┓
- * ┏┛┗━━━━━━━┛┗━━━┓
- * ┃ ┃
- * ┃ ━ ┃
- * ┃ > < ┃
- * ┃ ┃
- * ┃... ⌒ ... ┃
- * ┃ ┃
- * ┗━┓ ┏━┛
- * ┃ ┃ Code is far away from bug with the animal protecting
- * ┃ ┃ 神兽保佑, 代码无 bug
- * ┃ ┃
- * ┃ ┃
- * ┃ ┃
- * ┃ ┃
- * ┃ ┗━━━┓
- * ┃ ┣┓
- * ┃ ┏┛
- * ┗┓┓┏━┳┓┏┛
- * ┃┫┫ ┃┫┫
- * ┗┻┛ ┗┻┛
- */
- // warm heart, wagging tail,and a smile just for you!
- //
- // _ooOoo_
- // o8888888o
- // 88"."88
- // (| -_- |)
- // O\ = /O
- // ____/`---'\____
- // .' \| |// `.
- // / \||| : |||// // / _||||| -:- |||||- // | | \ - /// | |
- // | \_| ''\---/'' | |
- // \ .-\__ `-` ___/-. /
- // ___`. .' /--.--\ `. . __
- // .""'<`.___\_<|>_/___.'>'"".
- // | | : `- \`.;`\ _ /`;.`/ - ` : | |
- // \ \ `-. \_ __\ /__ _/ .-` //
- // ======`-.____`-.___\_____/___.-`____.-'======
- // `=---='
- // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
- // 佛祖保佑 永无 BUG
- #include <set>
- #include <map>
- #include <stack>
- #include <cmath>
- #include <queue>
- #include <cstdio>
- #include <string>
- #include <bitset>
- #include <vector>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- typedef long long LL;
- typedef pair<int, int> pii;
- typedef unsigned long long uLL;
- #define bug printf("*********\n")
- #define FIN freopen("input.txt","r",stdin);
- #define FON freopen("output.txt","w+",stdout);
- #define IO iOS::sync_with_stdio(false),cin.tie(0)
- #define debug1(x) cout<<"["<<#x<<""<<(x)<<"]\n"#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"
- const int maxn = 1e5 + 5;
- const int INF = 0x3f3f3f3f;
- const int mod = 1e9 + 7;
- const double Pi = acos(-1);
- LL gcd(LL a, LL b) {
- return b ? gcd(b, a % b) : a;
- }
- LL lcm(LL a, LL b) {
- return a / gcd(a, b) * b;
- }
- double dpow(double a, LL b) {
- double ans = 1.0;
- while(b) {
- if(b % 2)ans = ans * a;
- a = a * a;
- b /= 2;
- } return ans;
- }
- LL quick_pow(LL x, LL y) {
- LL ans = 1;
- while(y) {
- if(y & 1) {
- ans = ans * x % mod;
- } x = x * x % mod;
- y>>= 1;
- } return ans;
- }
- struct node {
- int l, r, sum, val;
- LL ans;
- } tree[maxn * 50];
- int root[maxn];
- int col[maxn];
- int tree_cnt;
- struct EDGE {
- int v, nxt;
- } edge[maxn <<1];
- int head[maxn], tot;
- void add_edge(int u, int v) {
- edge[tot].v = v;
- edge[tot].nxt = head[u];
- head[u] = tot++;
- }
- #define ls tree[rt].l
- #define rs tree[rt].r
- void push_up(int rt) {
- if(tree[ls].sum == tree[rs].sum) {
- tree[rt].sum = tree[ls].sum;
- tree[rt].val = tree[ls].sum;
- tree[rt].ans = tree[ls].ans + tree[rs].ans;
- } else if(tree[ls].sum> tree[rs].sum) {
- tree[rt].sum = tree[ls].sum;
- tree[rt].val = tree[ls].val;
- tree[rt].ans = tree[ls].ans;
- } else {
- tree[rt].sum = tree[rs].sum;
- tree[rt].val = tree[rs].val;
- tree[rt].ans = tree[rs].ans;
- }
- }
- void update(int &x, int l, int r, int pos, int val) {
- if(!x) x = ++tree_cnt;
- if(l == r) {
- tree[x].val = l;
- tree[x].sum += val;
- tree[x].ans = l;
- return;
- }
- int mid = (l + r)>> 1;
- if(pos <= mid) update(tree[x].l, l, mid, pos, val);
- else update(tree[x].r, mid + 1, r, pos, val);
- push_up(x);
- }
- int merge(int x, int y, int l, int r) {
- if(!x) return y;
- if(!y) return x;
- if(l == r) {
- tree[x].val = l;
- tree[x].sum += tree[y].sum;
- tree[x].ans = l;
- return x;
- }
- int mid = (l + r)>> 1;
- tree[x].l = merge(tree[x].l, tree[y].l, l, mid);
- tree[x].r = merge(tree[x].r, tree[y].r, mid + 1, r);
- push_up(x);
- return x;
- }
- int Max = 100000;
- LL ans[maxn];
- void dfs(int u, int fa) {
- for(int i = head[u]; i != -1; i = edge[i].nxt) {
- int v = edge[i].v;
- if(v == fa) continue;
- dfs(v, u);
- merge(root[u], root[v], 1, Max);
- }
- update(root[u], 1, Max, col[u], 1);
- ans[u] = tree[root[u]].ans;
- }
- void init() {
- memset(head, -1, sizeof(head));
- memset(col, 0, sizeof(col));
- tree_cnt = tot = 0;
- }
- int main() {
- #ifndef ONLINE_JUDGE
- FIN
- #endif
- int n;
- scanf("%d", &n);
- init();
- for(int i = 1; i <= n; i++) {
- scanf("%d", &col[i]);
- root[i] = i;
- tree_cnt++;
- }
- for(int i = 1, u, v; i <n; i++) {
- scanf("%d%d", &u, &v);
- add_edge(u, v);
- add_edge(v, u);
- }
- dfs(1, 0);
- for(int i = 1; i <= n; i++) {
- printf("%lld%c", ans[i], i == n ? '\n' : ' ');
- }
- return 0;
- }
- P3521 [POI2011]ROT-Tree Rotations
题意:
给你一颗树, 只有叶子节点有权值, 你可以交换一个点的左右子树, 问你最小的逆序对数
题解:
线段树维护权值个个数即可
然后左右子树合并时计算交换和不交换的贡献取一个 min 即可
代码:
- /**
- * ┏┓ ┏┓
- * ┏┛┗━━━━━━━┛┗━━━┓
- * ┃ ┃
- * ┃ ━ ┃
- * ┃ > < ┃
- * ┃ ┃
- * ┃... ⌒ ... ┃
- * ┃ ┃
- * ┗━┓ ┏━┛
- * ┃ ┃ Code is far away from bug with the animal protecting
- * ┃ ┃ 神兽保佑, 代码无 bug
- * ┃ ┃
- * ┃ ┃
- * ┃ ┃
- * ┃ ┃
- * ┃ ┗━━━┓
- * ┃ ┣┓
- * ┃ ┏┛
- * ┗┓┓┏━┳┓┏┛
- * ┃┫┫ ┃┫┫
- * ┗┻┛ ┗┻┛
- */
- // warm heart, wagging tail,and a smile just for you!
- //
- // _ooOoo_
- // o8888888o
- // 88"."88
- // (| -_- |)
- // O\ = /O
- // ____/`---'\____
- // .' \| |// `.
- // / \||| : |||// // / _||||| -:- |||||- // | | \ - /// | |
- // | \_| ''\---/'' | |
- // \ .-\__ `-` ___/-. /
- // ___`. .' /--.--\ `. . __
- // .""'< `.___\_<|>_/___.'>'"".
- // | | : `- \`.;`\ _ /`;.`/ - ` : | |
- // \ \ `-. \_ __\ /__ _/ .-` //
- // ======`-.____`-.___\_____/___.-`____.-'======
- // `=---='
- // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
- // 佛祖保佑 永无 BUG
- #include <set>
- #include <map>
- #include <stack>
- #include <cmath>
- #include <queue>
- #include <cstdio>
- #include <string>
- #include <bitset>
- #include <vector>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- typedef long long LL;
- typedef pair<int, int> pii;
- typedef unsigned long long uLL;
- #define lson l,mid,rt<<1
- #define rson mid+1,r,rt<<1|1
- #define bug printf("*********\n")
- #define FIN freopen("input.txt","r",stdin);
- #define FON freopen("output.txt","w+",stdout);
- #define IO iOS::sync_with_stdio(false),cin.tie(0)
- #define debug1(x) cout<<"["<<#x<<""<<(x)<<"]\n"#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"
- const int maxn = 3e5 + 5;
- const int INF = 0x3f3f3f3f;
- const int mod = 1e9 + 7;
- const double Pi = acos(-1);
- LL gcd(LL a, LL b) {
- return b ? gcd(b, a % b) : a;
- }
- LL lcm(LL a, LL b) {
- return a / gcd(a, b) * b;
- }
- double dpow(double a, LL b) {
- double ans = 1.0;
- while(b) {
- if(b % 2)ans = ans * a;
- a = a * a;
- b /= 2;
- } return ans;
- }
- LL quick_pow(LL x, LL y) {
- LL ans = 1;
- while(y) {
- if(y & 1) {
- ans = ans * x % mod;
- } x = x * x % mod;
- y>>= 1;
- } return ans;
- }
- struct node {
- int l, r, sum;
- } tree[maxn * 40];
- int tree_cnt;
- int root[maxn];
- void update(int &x, int l, int r, int val) {
- if(!x) x = ++tree_cnt;
- tree[x].sum++;
- if(l == r) return;
- int mid = (l + r)>> 1;
- if(val <= mid) update(tree[x].l, l, mid, val);
- else update(tree[x].r, mid + 1, r, val);
- }
- int n;
- LL num1, num2, ans = 0;
- void merge(int &x, int y) {
- if(!x || !y) {
- x = x + y;
- return;
- }
- tree[x].sum += tree[y].sum;
- num1 += 1LL * tree[tree[x].l].sum * tree[tree[y].r].sum;
- num2 += 1LL * tree[tree[x].r].sum * tree[tree[y].l].sum;
- merge(tree[x].l, tree[y].l);
- merge(tree[x].r, tree[y].r);
- }
- void dfs(int &x) {
- int val;
- scanf("%d", &val);
- int ls = 0, rs = 0;
- if(!val) {
- dfs(ls);
- dfs(rs);
- num1 = num2 = 0;
- x = ls;
- merge(x, rs);
- ans += min(num1, num2);
- } else {
- update(x, 1, n, val);
- }
- }
- int main() {
- #ifndef ONLINE_JUDGE
- FIN
- #endif
- scanf("%d", &n);
- int x = 0;
- dfs(x);
- printf("%lld\n", ans);
- return 0;
- }
P4556 [Vani 有约会]雨天的尾巴
题意:
首先村落里的一共有 n 座房屋, 并形成一个树状结构. 然后救济粮分 m 次发放, 每次选择两个房屋 (x,y), 然后对于 x 到 y 的路径上(含 x 和 y) 每座房子里发放一袋 z 类型的救济粮.
然后深绘里想知道, 当所有的救济粮发放完毕后, 每座房子里存放的最多的是哪种救济粮.
题解:
树链剖分的写法很明显了, 维护一个 max 即可
讲一下线段树合并的写法
区间更新用单点更新和差分来代替, 求一个 LCA,x->y 的更新即可用在点 x+1, 点 y+1, 点 lca(x,y)-1, 点 fa(lca(x,y))-1 后, 线段树合并来取代, 线段树维护最多的救济粮编号 val, 最多救济粮的数量 sum, 然后在合并的时候就可以统计出 u 节点的答案了
代码
- /**
- * ┏┓ ┏┓
- * ┏┛┗━━━━━━━┛┗━━━┓
- * ┃ ┃
- * ┃ ━ ┃
- * ┃ > < ┃
- * ┃ ┃
- * ┃... ⌒ ... ┃
- * ┃ ┃
- * ┗━┓ ┏━┛
- * ┃ ┃ Code is far away from bug with the animal protecting
- * ┃ ┃ 神兽保佑, 代码无 bug
- * ┃ ┃
- * ┃ ┃
- * ┃ ┃
- * ┃ ┃
- * ┃ ┗━━━┓
- * ┃ ┣┓
- * ┃ ┏┛
- * ┗┓┓┏━┳┓┏┛
- * ┃┫┫ ┃┫┫
- * ┗┻┛ ┗┻┛
- */
- // warm heart, wagging tail,and a smile just for you!
- //
- // _ooOoo_
- // o8888888o
- // 88"."88
- // (| -_- |)
- // O\ = /O
- // ____/`---'\____
- // .' \| |// `.
- // / \||| : |||// // / _||||| -:- |||||- // | | \ - /// | |
- // | \_| ''\---/'' | |
- // \ .-\__ `-` ___/-. /
- // ___`. .' /--.--\ `. . __
- // .""'<`.___\_<|>_/___.'>'"".
- // | | : `- \`.;`\ _ /`;.`/ - ` : | |
- // \ \ `-. \_ __\ /__ _/ .-` //
- // ======`-.____`-.___\_____/___.-`____.-'======
- // `=---='
- // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
- // 佛祖保佑 永无 BUG
- #include <set> #include <map> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <string> #include <bitset> #include <vector> #include <cstring> #include <iostream> #include <algorithm> using namespace std;
- typedef long long LL;
- typedef pair <int,
- int> pii;
- typedef unsigned long long uLL;#define lson l,
- mid,
- rt <<1#define rson mid + 1,
- r,
- rt << 1 | 1#define bug printf("*********\n")#define FIN freopen("input.txt", "r", stdin);#define FON freopen("output.txt", "w+", stdout);#define IO iOS: :sync_with_stdio(false),
- cin.tie(0)#define debug1(x) cout << "[" << #x << "" << (x) <<"]\n"#define debug2(x, y) cout <<"["<< #x <<" "<< (x) <<" "<< #y <<" "<< (y) <<"]\n"#define debug3(x, y, z) cout <<"["<< #x <<" "<< (x) <<" "<< #y <<" "<< (y) <<" "<< #z <<" "<< z <<"]\n"const int maxn = 3e5 + 5;
- const int INF = 0x3f3f3f3f;
- const int mod = 1e9 + 7;
- const double Pi = acos( - 1);
- LL gcd(LL a, LL b) {
- return b ? gcd(b, a % b) : a;
- }
- LL lcm(LL a, LL b) {
- return a / gcd(a, b) * b;
- }
- double dpow(double a, LL b) {
- double ans = 1.0;
- while (b) {
- if (b % 2) ans = ans * a;
- a = a * a;
- b /= 2;
- }
- return ans;
- }
- LL quick_pow(LL x, LL y) {
- LL ans = 1;
- while (y) {
- if (y & 1) {
- ans = ans * x % mod;
- }
- x = x * x % mod;
- y>>= 1;
- }
- return ans;
- }
- struct EDGE {
- int v,
- nxt;
- }
- edge[maxn <<1];
- int head[maxn],
- tot;
- void add_edge(int u, int v) {
- edge[tot].v = v;
- edge[tot].nxt = head[u];
- head[u] = tot++;
- }
- struct node {
- int l,
- r,
- sum,
- val;
- }
- tree[maxn * 40];
- int root[maxn];
- int tree_cnt;
- int sz[maxn],
- dep[maxn],
- fa[maxn],
- top[maxn],
- w[maxn],
- son[maxn],
- W[maxn],
- cnt;
- void init() {
- dep[1] = 1;
- fa[1] = 0;
- memset(head, -1, sizeof(head));
- tree_cnt = 0;
- tot = 0;
- cnt = 0;
- }#define ls tree[rt].l#define rs tree[rt].r void push_up(int rt) {
- if (tree[ls].sum> tree[rs].sum) {
- tree[rt].sum = tree[ls].sum;
- tree[rt].val = tree[ls].val;
- } else if (tree[ls].sum == tree[rs].sum) {
- tree[rt].sum = tree[ls].sum;
- tree[rt].val = min(tree[ls].val, tree[rs].val);
- } else {
- tree[rt].sum = tree[rs].sum;
- tree[rt].val = tree[rs].val;
- }
- }
- void update(int & x, int l, int r, int pos, int val) {
- if (!x) x = ++tree_cnt;
- if (l == r) {
- tree[x].sum += val;
- if (tree[x].sum) {
- tree[x].val = l;
- } else {
- tree[x].val = 0;
- }
- return;
- }
- int mid = (l + r)>> 1;
- if (pos <= mid) update(tree[x].l, l, mid, pos, val);
- else update(tree[x].r, mid + 1, r, pos, val);
- push_up(x);
- }
- void merge(int & x, int y, int l, int r) {
- if (!x || !y) {
- x = x + y;
- return;
- }
- if (l == r) {
- tree[x].sum += tree[y].sum;
- if (tree[x].sum) {
- tree[x].val = l;
- } else {
- tree[x].val = 0;
- }
- return;
- }
- int mid = (l + r)>> 1;
- merge(tree[x].l, tree[y].l, l, mid);
- merge(tree[x].r, tree[y].r, mid + 1, r);
- push_up(x);
- }
- void dfs1(int u) {
- sz[u] = 1;
- son[u] = 0;
- for (int i = head[u];~i; i = edge[i].nxt) {
- int v = edge[i].v;
- if (v != fa[u]) {
- fa[v] = u;
- dep[v] = dep[u] + 1;
- dfs1(v);
- sz[u] += sz[v];
- if (sz[v]> sz[son[u]]) son[u] = v;
- }
- }
- }
- void dfs2(int u, int tp, int x) {
- top[u] = tp;
- w[u] = ++cnt;
- W[cnt] = u;
- if (son[u]) dfs2(son[u], tp, 1);
- for (int i = head[u];~i; i = edge[i].nxt) {
- int v = edge[i].v;
- if (v == son[u] || v == fa[u]) continue;
- dfs2(v, v, 2);
- }
- }
- int LCA(int x, int y) {
- while (top[x] != top[y]) {
- if (dep[top[x]] <dep[top[y]]) std: :swap(x, y);
- x = fa[top[x]];
- }
- if (dep[x]> dep[y]) std: :swap(x, y);
- return x;
- }
- int ans[maxn];
- void dfs(int u, int fa) {
- for (int i = head[u]; i != -1; i = edge[i].nxt) {
- int v = edge[i].v;
- if (v == fa) continue;
- dfs(v, u);
- merge(root[u], root[v], 1, 100000);
- }
- ans[u] = tree[root[u]].val;
- }
- int main() {#ifndef ONLINE_JUDGE FIN#endif int n,
- m;
- init();
- scanf("%d%d", &n, &m);
- for (int i = 1; i <n; i++) {
- int u,
- v;
- scanf("%d%d", &u, &v);
- add_edge(u, v);
- add_edge(v, u);
- }
- dfs1(1);
- dfs2(1, 1, 1);
- for (int i = 1; i <= m; i++) {
- int x,
- y,
- z;
- scanf("%d%d%d", &x, &y, &z);
- int lca = LCA(x, y);
- update(root[x], 1, 100000, z, 1);
- // bug;
- update(root[y], 1, 100000, z, 1);
- update(root[lca], 1, 100000, z, -1);
- if (fa[lca]) update(root[fa[lca]], 1, 100000, z, -1);
- }
- dfs(1, 0);
- for (int i = 1; i <= n; i++) {
- printf("%d\n", ans[i]);
- }
- return 0;
- }
2016 湖南省赛 I Tree Intersection(线段树合并, 树链剖分)
题意:
给你一个 n 个结点的树, 树上每个节点有自己的颜色
问你删除第 i 条边后形成的两颗子树有多少个相同的颜色
题解:
树链剖分写法:
对于每一种颜色来说, 如果这个颜色是在单独的一颗子树中, 那么就不会对其他的边产生贡献, 所以我们单独对每一种颜色对边的贡献讨论, 如果这个颜色只有一个, 那么就不会产生贡献, 否则, 他就可以在两个相同颜色之间的路径上的边产生贡献, 用树剖剖下来后区间加一加就可以了
线段树合并的写法
对于每一种颜色建权值线段树, 线段树合并统计答案即可
代码
树链剖分写法:
- /**
- * ┏┓ ┏┓
- * ┏┛┗━━━━━━━┛┗━━━┓
- * ┃ ┃
- * ┃ ━ ┃
- * ┃ > < ┃
- * ┃ ┃
- * ┃... ⌒ ... ┃
- * ┃ ┃
- * ┗━┓ ┏━┛
- * ┃ ┃ Code is far away from bug with the animal protecting
- * ┃ ┃ 神兽保佑, 代码无 bug
- * ┃ ┃
- * ┃ ┃
- * ┃ ┃
- * ┃ ┃
- * ┃ ┗━━━┓
- * ┃ ┣┓
- * ┃ ┏┛
- * ┗┓┓┏━┳┓┏┛
- * ┃┫┫ ┃┫┫
- * ┗┻┛ ┗┻┛
- */
- // warm heart, wagging tail,and a smile just for you!
- //
- // _ooOoo_
- // o8888888o
- // 88"."88
- // (| -_- |)
- // O\ = /O
- // ____/`---'\____
- // .' \| |// `.
- // / \||| : |||// // / _||||| -:- |||||- // | | \ - /// | |
- // | \_| ''\---/'' | |
- // \ .-\__ `-` ___/-. /
- // ___`. .' /--.--\ `. . __
- // .""'< `.___\_<|>_/___.'>'"".
- // | | : `- \`.;`\ _ /`;.`/ - ` : | |
- // \ \ `-. \_ __\ /__ _/ .-` //
- // ======`-.____`-.___\_____/___.-`____.-'======
- // `=---='
- // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
- // 佛祖保佑 永无 BUG
- #include <set> #include <map> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <string> #include <vector> #include <cstring> #include <iostream> #include <algorithm> using namespace std;
- typedef long long LL;
- typedef pair <int,
- int> pii;
- typedef unsigned long long uLL;#define ls rt <<1#define rs rt << 1 | 1#define lson l,
- mid,
- rt << 1#define rson mid + 1,
- r,
- rt << 1 | 1#define bug printf("*********\n")#define FIN freopen("input.txt", "r", stdin);#define FON freopen("output.txt", "w+", stdout);#define IO iOS: :sync_with_stdio(false),
- cin.tie(0)#define debug1(x) cout << "[" << #x << "" << (x) <<"]\n"#define debug2(x, y) cout <<"["<< #x <<" "<< (x) <<" "<< #y <<" "<< (y) <<"]\n"#define debug3(x, y, z) cout <<"["<< #x <<" "<< (x) <<" "<< #y <<" "<< (y) <<" "<< #z <<" "<< z <<"]\n"const int maxn = 3e5 + 5;
- const int INF = 0x3f3f3f3f;
- const int mod = 1e9 + 7;
- const double Pi = acos( - 1);
- LL gcd(LL a, LL b) {
- return b ? gcd(b, a % b) : a;
- }
- LL lcm(LL a, LL b) {
- return a / gcd(a, b) * b;
- }
- double dpow(double a, LL b) {
- double ans = 1.0;
- while (b) {
- if (b % 2) ans = ans * a;
- a = a * a;
- b /= 2;
- }
- return ans;
- }
- LL quick_pow(LL x, LL y) {
- LL ans = 1;
- while (y) {
- if (y & 1) {
- ans = ans * x % mod;
- }
- x = x * x % mod;
- y>>= 1;
- }
- return ans;
- }
- int n;
- int a[maxn],
- sz[maxn],
- dep[maxn],
- fa[maxn],
- top[maxn],
- w[maxn],
- son[maxn],
- W[maxn];
- int sum[maxn <<2],
- lazy[maxn << 2],
- vis[maxn << 2];
- struct EDGE {
- int u,
- v,
- nt;
- }
- edge[maxn << 1];
- int head[maxn],
- summ,
- cnt;
- int u[maxn];
- int v[maxn];
- void add_edge(int u, int v) {
- edge[++summ].u = u;
- edge[summ].v = v;
- edge[summ].nt = head[u];
- head[u] = summ;
- }
- void dfs1(int u) {
- sz[u] = 1;
- son[u] = 0;
- for (int i = head[u];~i; i = edge[i].nt) {
- int v = edge[i].v;
- if (v != fa[u]) {
- fa[v] = u;
- dep[v] = dep[u] + 1;
- dfs1(v);
- sz[u] += sz[v];
- if (sz[v]> sz[son[u]]) son[u] = v;
- }
- }
- }
- void dfs2(int u, int tp, int x) {
- top[u] = tp;
- w[u] = ++cnt;
- W[cnt] = u;
- if (son[u]) dfs2(son[u], tp, 1);
- for (int i = head[u];~i; i = edge[i].nt) {
- int v = edge[i].v;
- if (v == son[u] || v == fa[u]) continue;
- dfs2(v, v, 2);
- }
- }
- vector <int> vec[maxn];
- void init() {
- memset(head, -1, sizeof(head));
- summ = 1;
- cnt = 0;
- for (int i = 1; i <= n; i++) {
- vec[i].clear();
- }
- for (int i = 1; i <= n; i++) {
- scanf("%d", &a[i]);
- vec[a[i]].push_back(i);
- }
- for (int i = 1; i <n; i++) {
- // int u, v;
- scanf("%d %d", &u[i], &v[i]);
- add_edge(u[i], v[i]);
- add_edge(v[i], u[i]);
- }
- dep[1] = 1;
- fa[1] = 0;
- dfs1(1);
- dfs2(1, 1, 1);
- }
- void pushup(int rt) {
- if (vis[ls] == vis[rs]) vis[rt] = vis[ls];
- else vis[rt] = -1;
- }
- void pushdown(int rt, int mid) {
- if (lazy[rt]) {
- lazy[rt << 1] = lazy[rt];
- lazy[rt << 1 | 1] = lazy[rt];
- vis[rt << 1] = 0;
- vis[rt << 1 | 1] = 0;
- lazy[rt] = 0;
- }
- }
- void build(int l, int r, int rt) {
- lazy[rt] = 0;
- sum[rt] = 0;
- if (l == r) {
- vis[rt] = 0;
- return;
- }
- int mid = (l + r)>> 1;
- build(lson);
- build(rson);
- }
- void update(int L, int R, int val, int l, int r, int rt) {
- // debug2(L, R);
- if (L> R || r <L || R < l) return;
- if (vis[rt] == 1) return;
- if (L <= l && r <= R) {
- // sum[rt] += val * (r - l + 1);
- // lazy[rt] += val;
- if (vis[rt] == 0) {
- vis[rt] = 1;
- sum[rt]++;
- return;
- }
- }
- pushdown(rt, r - l + 1);
- int mid = (l + r)>> 1;
- if (L <= mid) update(L, R, val, lson);
- if (R> mid) update(L, R, val, rson);
- pushup(rt);
- }
- int query(int pos, int l, int r, int rt) {
- if (l == r) {
- return sum[rt];
- }
- pushdown(rt, r - l + 1);
- int mid = (l + r)>> 1;
- int ans = sum[rt];
- if (pos <= mid) ans += query(pos, lson);
- else ans += query(pos, rson);
- return ans;
- }
- int LCA(int x, int y) {
- // debug2(x, y);
- while (top[x] != top[y]) {
- // bug;
- if (dep[top[x]] <dep[top[y]]) swap(x, y);
- update(w[top[x]], w[x], 1, 1, n, 1);
- x = fa[top[x]];
- }
- if (dep[x]> dep[y]) std: :swap(x, y);
- update(w[x] + 1, w[y], 1, 1, n, 1);
- return x;
- }
- int main() {#ifndef ONLINE_JUDGE FIN#endif
- while (scanf("%d", &n) != EOF) {
- init();
- build(1, n, 1);
- // for(int i = 1; i <= n; i++) {
- // // printf("%d\n", w[]);
- // // debug1(w[i]);
- // }
- for (int i = 1; i <= n; i++) {
- vis[1] = 0;
- lazy[1] = 1;
- int sz = vec[i].size();
- if (sz <2) continue;
- int bb = LCA(vec[i][0], vec[i][1]);
- for (int j = 2; j < sz; j++) {
- // debug2(vec[i][0], vec[i][1]);
- bb = LCA(bb, vec[i][j]);
- }
- }
- for (int i = 1; i < n; i++) {
- int ans;
- // debug2(v[i], u[i]);
- if (fa[v[i]] == u[i]) {
- ans = query(w[v[i]], 1, n, 1);
- } else {
- ans = query(w[u[i]], 1, n, 1);
- }
- printf("%d\n", ans);
- }
- }
- return 0;
- }
线段树合并写法
- /**
- * ┏┓ ┏┓
- * ┏┛┗━━━━━━━┛┗━━━┓
- * ┃ ┃
- * ┃ ━ ┃
- * ┃ > < ┃
- * ┃ ┃
- * ┃... ⌒ ... ┃
- * ┃ ┃
- * ┗━┓ ┏━┛
- * ┃ ┃ Code is far away from bug with the animal protecting
- * ┃ ┃ 神兽保佑, 代码无 bug
- * ┃ ┃
- * ┃ ┃
- * ┃ ┃
- * ┃ ┃
- * ┃ ┗━━━┓
- * ┃ ┣┓
- * ┃ ┏┛
- * ┗┓┓┏━┳┓┏┛
- * ┃┫┫ ┃┫┫
- * ┗┻┛ ┗┻┛
- */
- // warm heart, wagging tail,and a smile just for you!
- //
- // _ooOoo_
- // o8888888o
- // 88"."88
- // (| -_- |)
- // O\ = /O
- // ____/`---'\____
- // .' \| |// `.
- // / \||| : |||// // / _||||| -:- |||||- // | | \ - /// | |
- // | \_| ''\---/'' | |
- // \ .-\__ `-` ___/-. /
- // ___`. .' /--.--\ `. . __
- // .""'< `.___\_<|>_/___.'>'"".
- // | | : `- \`.;`\ _ /`;.`/ - ` : | |
- // \ \ `-. \_ __\ /__ _/ .-` //
- // ======`-.____`-.___\_____/___.-`____.-'======
- // `=---='
- // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
- // 佛祖保佑 永无 BUG
- #include <set>
- #include <map>
- #include <stack>
- #include <cmath>
- #include <queue>
- #include <cstdio>
- #include <string>
- #include <bitset>
- #include <vector>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- typedef long long LL;
- typedef pair<int, int> pii;
- typedef unsigned long long uLL;
- #define ls rt<<1
- #define rs rt<<1|1
- #define lson l,mid,rt<<1
- #define rson mid+1,r,rt<<1|1
- #define bug printf("*********\n")
- #define FIN freopen("input.txt","r",stdin);
- #define FON freopen("output.txt","w+",stdout);
- #define IO iOS::sync_with_stdio(false),cin.tie(0)
- #define debug1(x) cout<<"["<<#x<<""<<(x)<<"]\n"#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"
- const int maxn = 1e5 + 5;
- const int INF = 0x3f3f3f3f;
- const int mod = 1e9 + 7;
- const double Pi = acos(-1);
- LL gcd(LL a, LL b) {
- return b ? gcd(b, a % b) : a;
- }
- LL lcm(LL a, LL b) {
- return a / gcd(a, b) * b;
- }
- double dpow(double a, LL b) {
- double ans = 1.0;
- while(b) {
- if(b % 2)ans = ans * a;
- a = a * a;
- b /= 2;
- } return ans;
- }
- LL quick_pow(LL x, LL y) {
- LL ans = 1;
- while(y) {
- if(y & 1) {
- ans = ans * x % mod;
- } x = x * x % mod;
- y>>= 1;
- } return ans;
- }
- int col[maxn];
- int cnt[maxn];
- struct EDGE {
- int v, nxt;
- } edge[maxn <<1];
- int head[maxn], tot;
- void init() {
- memset(head, -1, sizeof(head));
- tot = 0;
- }
- void add_edge(int u, int v) {
- edge[tot].v = v;
- edge[tot].nxt = head[u];
- head[u] = tot++;
- }
- struct node {
- int l, r, sum, val;
- } tree[maxn * 20];
- int root[maxn];
- int rt_cnt = 0;
- int n;
- int ans[maxn];
- void push_up(int rt) {
- tree[rt].sum = tree[tree[rt].l].sum + tree[tree[rt].r].sum;
- }
- int build(int l, int r, int pos) {
- int rt = ++rt_cnt;
- tree[rt].l = 0;
- tree[rt].r = 0;
- tree[rt].sum = 0;
- if(l == r) {
- tree[rt].val = 1;
- if(tree[rt].val != cnt[l]) {
- tree[rt].sum = 1;
- } else {
- tree[rt].sum = 0;
- }
- return rt;
- }
- int mid = (l + r)>> 1;
- if(pos <= mid) tree[rt].l = build(l, mid, pos);
- else tree[rt].r = build(mid + 1, r, pos);
- push_up(rt);
- return rt;
- }
- void merge(int &x, int y, int l, int r) {
- if(!x || !y) {
- if(!x) x = y;
- return;
- }
- if(l == r) {
- tree[x].val += tree[y].val;
- tree[x].sum = (tree[x].val != cnt[l]);
- return;
- }
- int mid = (l + r)>> 1;
- merge(tree[x].l, tree[y].l, l, mid);
- merge(tree[x].r, tree[y].r, mid + 1, r);
- push_up(x);
- }
- void dfs(int u, int fa, int id) {
- root[u] = build(1, n, col[u]);
- for(int i = head[u]; i != -1; i = edge[i].nxt) {
- int v = edge[i].v;
- if(v == fa) continue;
- dfs(v, u, i);
- merge(root[u], root[v], 1, n);
- }
- if(u != 1) {
- int tid = id / 2 + 1;
- ans[tid] = tree[root[u]].sum;
- }
- }
- int main() {
- #ifndef ONLINE_JUDGE
- FIN
- #endif
- scanf("%d", &n);
- for(int i = 1; i <= n; i++) {
- scanf("%d", &col[i]);
- // vec[col[i]].push_back(i);
- cnt[col[i]]++;
- }
- init();
- for(int i = 1, u, v; i < n; i++) {
- scanf("%d%d", &u, &v);
- add_edge(u, v);
- add_edge(v, u);
- }
- // debug1(n);
- dfs(1, -1, -1);
- for(int i = 1; i <= n - 1; i++) {
- printf("%d\n", ans[i]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3235703.html