首页 > 代码库 > （树上莫队）HDU - 5799 This world need more Zhu
（树上莫队）HDU - 5799 This world need more Zhu
题意：
两种询问：
1、询问以u为根的子树中出现的a次的数的和与出现b次的数的和的gcd。
2、询问u到v的树链中出现的a次的数的和与出现b次的数的和的gcd。
有点绕。。
分析：
因为自己不会树上莫队，所以学习了一波。
但是对于子树我还是有所经验，可以转成dfs序来做，之前有做过类似的题，比如这题。
然而对于树链有点懵逼，虽然我觉得也能用dfs序做，不过看大佬们的dfs序做的树链查询，也有点懵，感觉写起来很麻烦。
貌似是修改了dfs序，回溯的时候不再只是和进入时相同的序，而是独立的序。
还是感觉麻烦。。后来发现一个基于树分块的树上莫队，感觉很强。代码显然没有前者复杂。所以就用了它。
第一种询问其实有nlogn的做法，跟上面的之前做过的 dfs序题是同一题。
但是这里写的代码好长啊。。虽然很挫。。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cmath> 5 #include <cstring> 6 #include <set> 7 #include <vector> 8 #include <queue> 9 #include <map> 10 #include <list> 11 #include <bitset> 12 #include <string> 13 #include <cctype> 14 #include <cstdlib> 15 16 using namespace std; 17 18 typedef long long ll; 19 typedef unsigned long long ull; 20 #define inf (0x3f3f3f3f) 21 #define lnf (0x3f3f3f3f3f3f3f3f) 22 #define eps (1e-8) 23 int sgn(double a) { 24 return a < -eps ? -1 : a < eps ? 0 : 1; 25 } 26 27 const int maxn = 100010; 28 29 int t; 30 struct Q { 31 int u, v, a, b; 32 int l, r; 33 int index; 34 }; 35 36 37 int col[maxn]; 38 int cnt[maxn]; 39 ll cs[maxn]; 40 ll ans[maxn]; 41 const int bk = 316; 42 43 const int DEG = 20; 44 vector<Q> query[3]; 45 vector<int> g[maxn]; 46 47 int n, q; 48 int a[maxn], b[maxn]; 49 50 inline bool scan_d(int &num) { 51 char in; 52 bool IsN = false; 53 in = getchar(); 54 if(in == EOF) return false; 55 while(in != ‘-‘ && (in < ‘0‘ || in > ‘9‘)) in = getchar(); 56 if(in == ‘-‘) { 57 IsN = true; 58 num = 0; 59 } else num = in - ‘0‘; 60 while(in = getchar(), in >= ‘0‘ && in <= ‘9‘) { 61 num *= 10, num += in - ‘0‘; 62 } 63 if(IsN) num = -num; 64 return true; 65 } 66 67 void initHash() { 68 for(int i = 1; i <= n; i++) { 69 b[i] = a[i]; 70 } 71 sort(b + 1, b + n + 1); 72 int p = unique(b + 1, b + n + 1) - b - 1; 73 for(int i = 1; i <= n; i++) { 74 a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b; 75 } 76 } 77 78 int L[maxn]; 79 int R[maxn]; 80 int d[maxn]; 81 int tot = 0; 82 83 void dfs(int u, int fa, int dep) { 84 L[u] = ++tot; 85 d[u] = dep; 86 col[tot] = a[u]; 87 for (int i = 0; i < g[u].size(); i++) { 88 int v = g[u][i]; 89 if (v == fa)continue; 90 dfs(v, u, dep + 1); 91 } 92 R[u] = tot; 93 } 94 95 96 97 bool cmp(Q a, Q b) { 98 if(a.l / bk == b.l / bk)return a.r < b.r; 99 else return a.l / bk < b.l / bk;100 }101 102 103 /// find_block104 int block[maxn], bcnt, bsize;105 int stk[maxn], top;106 107 void add_block(int &cnt) {108 while(cnt--) block[stk[--top]] = bcnt;109 bcnt++;110 cnt = 0;111 }112 113 void rest_block() {114 while(top) block[stk[--top]] = bcnt - 1;115 }116 117 int dfs_block(int u, int f) {118 int s = 0;119 for(int i = 0; i < g[u].size(); i++) {120 int v = g[u][i];121 if(v == f) continue;122 s += dfs_block(v, u);123 if(s >= bsize) add_block(s);124 }125 stk[top++] = u;126 s++;127 if(s >= bsize) add_block(s);128 return s;129 }130 131 void init_block() {132 bsize = bk;133 dfs_block(1, 0);134 rest_block();135 }136 137 138 /// ask_rmq139 int fa[DEG][maxn];140 int dep[maxn];141 142 void dfs_lca(int u, int f, int depth) {143 dep[u] = depth;144 fa[0][u] = f;145 for(int i = 0; i < g[u].size(); i++) {146 int v = g[u][i];147 if(v != f) dfs_lca(v, u, depth + 1);148 }149 }150 151 void init_lca() {152 dfs_lca(1, -1, 0);153 for(int k = 0; k + 1 < DEG; ++k) {154 for(int u = 1; u <= n; ++u) {155 if(fa[k][u] == -1) fa[k + 1][u] = -1;156 else fa[k + 1][u] = fa[k][fa[k][u]];157 }158 }159 }160 161 int ask_lca(int u, int v) {162 if(dep[u] < dep[v]) swap(u, v);163 for(int k = 0; k < DEG; ++k) {164 if((dep[u] - dep[v]) & (1 << k)) u = fa[k][u];165 }166 if(u == v) return u;167 for(int k = DEG - 1; k >= 0; --k) {168 if(fa[k][u] != fa[k][v])169 u = fa[k][u], v = fa[k][v];170 }171 return fa[0][u];172 }173 /// modui174 bool vis[maxn];175 176 void xorNode(int u) {177 if(vis[u]) {178 vis[u] = false;179 cs[cnt[a[u]]] -= b[a[u]];180 cnt[a[u]]--;181 cs[cnt[a[u]]] += b[a[u]];182 } else {183 vis[u] = true;184 cs[cnt[a[u]]] -= b[a[u]];185 cnt[a[u]]++;186 cs[cnt[a[u]]] += b[a[u]];187 }188 }189 190 void xorPathWithoutLca(int u, int v) {191 if(dep[u] < dep[v]) swap(u, v);192 while(dep[u] != dep[v])193 xorNode(u), u = fa[0][u];194 while(u != v)195 xorNode(u), u = fa[0][u], xorNode(v), v = fa[0][v];196 }197 198 void moveNode(int u, int v, int taru, int tarv) {199 xorPathWithoutLca(u, taru);200 xorPathWithoutLca(v, tarv);201 //printf("debug %d %d\n", ask_lca(u, v), ask_lca(taru, tarv));202 xorNode(ask_lca(u, v));203 xorNode(ask_lca(taru, tarv));204 }205 206 207 bool cmp2(Q a, Q b) {208 if(block[a.u] == block[b.u])return block[a.v] < block[b.v];209 else return block[a.u] < block[b.u];210 }211 212 213 void solve() {214 scan_d(t);215 int c = 0;216 while(t--) {217 tot = 0;218 memset(cs, 0, sizeof(cs));219 memset(cnt, 0, sizeof(cnt));220 memset(vis, 0, sizeof(vis));221 for(int i = 1; i <= n; i++) {222 g[i].clear();223 }224 query[1].clear();225 query[2].clear();226 scan_d(n);227 scan_d(q);228 for(int i = 1; i <= n; i++) {229 scan_d(a[i]);230 }231 initHash();232 for(int i = 0; i < n - 1; i++) {233 int u, v;234 scan_d(u);235 scan_d(v);236 g[u].push_back(v);237 g[v].push_back(u);238 }239 dfs(1, -1, 1);240 init_block();241 init_lca();242 for(int i = 0; i < q; i++) {243 int op, u, v, a, b;244 scan_d(op);245 scan_d(u);246 scan_d(v);247 scan_d(a);248 scan_d(b);249 query[op].push_back(Q{u, v, a, b, L[u], R[u], i});250 }251 sort(query[1].begin(), query[1].end(), cmp);252 253 254 int pl = 1, pr = 0;255 256 for (int i = 0; i < query[1].size(); i++) {257 int index = query[1][i].index;258 if (pr < query[1][i].r) {259 for (int j = pr + 1; j <= query[1][i].r; j++) {260 cs[cnt[col[j]]] -= b[col[j]];261 cnt[col[j]]++;262 cs[cnt[col[j]]] += b[col[j]];263 }264 } else {265 for (int j = pr; j > query[1][i].r; j--) {266 cs[cnt[col[j]]] -= b[col[j]];267 cnt[col[j]]--;268 cs[cnt[col[j]]] += b[col[j]];269 }270 }271 pr = query[1][i].r;272 if (pl < query[1][i].l) {273 for (int j = pl; j < query[1][i].l; j++) {274 cs[cnt[col[j]]] -= b[col[j]];275 cnt[col[j]]--;276 cs[cnt[col[j]]] += b[col[j]];277 }278 } else {279 for (int j = pl - 1; j >= query[1][i].l; j--) {280 cs[cnt[col[j]]] -= b[col[j]];281 cnt[col[j]]++;282 cs[cnt[col[j]]] += b[col[j]];283 }284 }285 pl = query[1][i].l;286 ans[index] = __gcd(cs[query[1][i].a], cs[query[1][i].b]);287 }288 memset(cs, 0, sizeof(cs));289 memset(cnt, 0, sizeof(cnt));290 291 292 for(int i = 0; i < query[2].size(); i++) {293 if(block[query[2][i].u] > block[query[2][i].v]) swap(query[2][i].u, query[2][i].v);294 }295 sort(query[2].begin(), query[2].end(), cmp2);296 297 int nowu = 1, nowv = 1;298 xorNode(1);299 for(int i = 0; i < query[2].size(); i++) {300 int index = query[2][i].index;301 moveNode(nowu, nowv, query[2][i].u, query[2][i].v);302 ans[index] = __gcd(cs[query[2][i].a], cs[query[2][i].b]);303 nowu = query[2][i].u, nowv = query[2][i].v;304 }305 printf("Case #%d:\n", ++c);306 for(int i = 0; i < q; i++) {307 printf("%lld\n", ans[i]);308 }309 310 }311 312 }313 314 315 316 int main() {317 318 #ifndef ONLINE_JUDGE319 freopen("1.in", "r", stdin);320 //freopen("1.out", "w", stdout);321 #endif322 //iostream::sync_with_stdio(false);323 solve();324 return 0;325 }
（树上莫队）HDU - 5799 This world need more Zhu
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。