JZOJ 5833. 【省选模拟8.20】Endless Fantasy
中二少年cenbo幻想自己统治着Euphoric Field。由此他开始了Endless Fantasy。
Euphoric Field有n座城市，m个民族。这些城市之间由n-1条道路连接形成了以城市1为根的有根树。
每个城市都是某一民族的聚居地，cenbo知道第i个城市的民族是A_i，人数是B_i。
为了维护稳定，cenbo需要知道某个区域内人数最多的民族。
他向你提出n个询问，其中第i个询问是：求以i为根的子树内，人数最多的民族有是哪个，这个民族有多少人。
如果子树内人数最多的民族有多个，输出其中编号最小的民族。
30%的数据，n<=1000；
60%的数据，n<=40000；
100%的数据，n<=400000，m<=n，1<=A_i<=m，0<=B_i<=1000。
题意有歧义吧……$b_i=0$想干啥……
题意：问子树众数
题解：直接dsu on tree
此题加强：loj 6290
1 %:pragma GCC optimize(2) 2 %:pragma GCC optimize(3) 3 %:pragma GCC optimize("Ofast") 4 %:pragma GCC optimize("inline") 5 %:pragma GCC optimize("-fgcse") 6 %:pragma GCC optimize("-fgcse-lm") 7 %:pragma GCC optimize("-fipa-sra") 8 %:pragma GCC optimize("-ftree-pre") 9 %:pragma GCC optimize("-ftree-vrp") 10 %:pragma GCC optimize("-fpeephole2") 11 %:pragma GCC optimize("-ffast-math") 12 %:pragma GCC optimize("-fsched-spec") 13 %:pragma GCC optimize("unroll-loops") 14 %:pragma GCC optimize("-falign-jumps") 15 %:pragma GCC optimize("-falign-loops") 16 %:pragma GCC optimize("-falign-labels") 17 %:pragma GCC optimize("-fdevirtualize") 18 %:pragma GCC optimize("-fcaller-saves") 19 %:pragma GCC optimize("-fcrossjumping") 20 %:pragma GCC optimize("-fthread-jumps") 21 %:pragma GCC optimize("-funroll-loops") 22 %:pragma GCC optimize("-fwhole-program") 23 %:pragma GCC optimize("-freorder-blocks") 24 %:pragma GCC optimize("-fschedule-insns") 25 %:pragma GCC optimize("inline-functions") 26 %:pragma GCC optimize("-ftree-tail-merge") 27 %:pragma GCC optimize("-fschedule-insns2") 28 %:pragma GCC optimize("-fstrict-aliasing") 29 %:pragma GCC optimize("-fstrict-overflow") 30 %:pragma GCC optimize("-falign-functions") 31 %:pragma GCC optimize("-fcse-skip-blocks") 32 %:pragma GCC optimize("-fcse-follow-jumps") 33 %:pragma GCC optimize("-fsched-interblock") 34 %:pragma GCC optimize("-fpartial-inlining") 35 %:pragma GCC optimize("no-stack-protector") 36 %:pragma GCC optimize("-freorder-functions") 37 %:pragma GCC optimize("-findirect-inlining") 38 %:pragma GCC optimize("-fhoist-adjacent-loads") 39 %:pragma GCC optimize("-frerun-cse-after-loop") 40 %:pragma GCC optimize("inline-small-functions") 41 %:pragma GCC optimize("-finline-small-functions") 42 %:pragma GCC optimize("-ftree-switch-conversion") 43 %:pragma GCC optimize("-foptimize-sibling-calls") 44 %:pragma GCC optimize("-fexpensive-optimizations") 45 %:pragma GCC optimize("-funsafe-loop-optimizations") 46 %:pragma GCC optimize("inline-functions-called-once") 47 %:pragma GCC optimize("-fdelete-null-pointer-checks") 48 49 #include <bits/stdc++.h> 50 51 using namespace std; 52 53 typedef long long ll; 54 55 const int N = 4e5 + 10; 56 57 int n, m; 58 59 int head[N], rest[2 * N], to[2 * N], tot; 60 61 int sz[N], son[N], cnt[N]; 62 63 int a[N], b[N]; 64 65 int zui_duo_de_min_zu[N], min_zu_de_ren_shu[N]; 66 67 int ans; 68 69 void add(int u, int v) { to[++ tot] = v, rest[tot] = head[u], head[u] = tot; } 70 71 void dfs(int u, int fa) { 72 sz[u] = 1; 73 for(int i = head[u] ; i ; i = rest[i]) { 74 int v = to[i]; 75 if(v == fa) continue; 76 dfs(v, u); 77 sz[u] += sz[v]; 78 if(sz[v] > sz[son[u]]) son[u] = v; 79 } 80 } 81 82 void ins(int u) { 83 cnt[a[u]] += b[u]; 84 int ct = cnt[a[u]]; 85 if(ans == 0 || cnt[ans] < ct || (cnt[ans] == ct && ans > a[u])) ans = a[u]; 86 } 87 88 void push(int u, int fa, int type) { 89 if(type == 0) ins(u); 90 else cnt[a[u]] = 0; 91 for(int i = head[u] ; i ; i = rest[i]) { 92 int v = to[i]; 93 if(v == fa) continue; 94 push(v, u, type); 95 } 96 } 97 98 void sol(int u, int fa) { 99 for(int i = head[u] ; i ; i = rest[i]) { 100 int v = to[i]; 101 if(v == son[u] || v == fa) continue; 102 sol(v, u); 103 push(v, u, 1); 104 ans = 0; 105 } 106 ans = 0; 107 108 if(son[u]) sol(son[u], u); 109 110 ins(u); 111 for(int i = head[u] ; i ; i = rest[i]) { 112 int v = to[i]; 113 if(v == son[u] || v == fa) continue; 114 push(v, u, 0); 115 } 116 117 zui_duo_de_min_zu[u] = ans; 118 min_zu_de_ren_shu[u] = cnt[ans]; 119 } 120 121 void read(int &x) { 122 char c = x = 0; 123 while(!isdigit(c)) c = getchar(); 124 while(isdigit(c)) x = x * 10 + c - '0', c = getchar(); 125 } 126 127 int main() { 128 // freopen("data.in", "r", stdin); 129 freopen("endless.in", "r", stdin); 130 freopen("endless.out", "w", stdout); 131 read(n), read(m); 132 for(int i = 1, u, v ; i < n ; ++ i) { 133 read(u), read(v); 134 add(u, v), add(v, u); 135 } 136 for(int i = 1 ; i <= n ; ++ i) read(a[i]), read(b[i]); 137 dfs(1, 0); 138 sol(1, 0); 139 for(int i = 1 ; i <= n ; ++ i) { 140 printf("%d %d\n", zui_duo_de_min_zu[i], min_zu_de_ren_shu[i]); 141 } 142 }JZOJ 5833. 【省选模拟8.20】Endless Fantasy 优质内容筛选与推荐>>
1、实现无人值守流程审批管理
2、字符串操作练习：星座、凯撒密码、99乘法表
3、Java 基础知识汇总
4、Bestcoder Tom and matrix
5、linux服务器上部署项目，同时运行两个或多个tomcat