(弄了一个月的搬瓦工搭个梯子顺便搭个博客玩……不务正业)
As we all know, Zhu is the most powerful man. He has the infinite power to protest the world. We need more men like Zhu! In Duoladuo, this place is like a tree. There are n points and n−1 edges. And the root is 1 . Each point can reach other points. Each point has a value a[i] named Zhu power. Liao is a curious baby, he has m questions to ask Zhu. But now Zhu is busy, he wants you to help him answer Liao’s questions. Liao’s question will be like op u v a b. if op is 1, the u is equal to v . Liao wants to know the gcd of the sum of numbers thats appears a times and the sum of numbers that appears b times in subtree u . if op is 2, Liao wants to know the gcd of the sum of numbers thats appears a times and the sum of numbers that appears b times on the path from u to v. gcd is greatest common divisor. notice: we can know gcd(x,0)=x .
In the first line contains a single positive integer T , indicating number of test case. In the second line there are two numbers n,m. n is the size of Duoladuo. m is the number of Liao’s questions. The next line contains n integers A1,A2,…AN, means the value of i point. In the next n−1 line contains tow numbers u,v . It means there is a edge between point u and point v. The next m lines will be the Liao’s question: 1 u v a b 2 u v a b 1≤T≤10,1≤n≤100000,1≤m≤100000,1≤op≤2,1≤u,v≤n,1≤a,b≤n,1≤Ai≤1000000000.
For each case, output Case #i:. ( i is the number of the test case, from 1 to T ). Then, you need to output the answer for every Liao’s questions.
对于操作1只要搞出来树的dfs序，每个询问对应一个连续区间，直接做序列莫队即可。 对于操作2就是树上莫队。 然后我按照之前的做法在搞出的括号序上跑莫队，T了。Baidu到一篇博客也说本地测10s，根本卡不过去。看了一下数据，后面五个点的莫队基本上都跑满了n∗n‾√。本来 n <script type="math/tex" id="MathJax-Element-36">n</script>给的范围就很大了，然后对于这种专门构造数据卡某种算法的我也是无Fuck说。那种树分块的暂时还不会，以后学一下。 另外那篇博客说做两次常数大其实不然，想一下也是分开做复杂度更优。 下面就贴个一起做的代码吧，写的还算比较短，不过很丑也过不去就是了。
#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> using namespace std; struct rec{ int id, col; }arr[100010]; struct que{ int x, y, l, r, lca, a, b, id; long long ans; }; int T, n, m, to[100010]; inline int rd(){ int a=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) (a*=10)+=c-'0', c=getchar(); return a; } // 离散化 void lis(){ sort(arr+1, arr+n+1, [](rec a, rec b){return a.col<b.col;}); int t=1; for(int i=1;i<=n;){ int p=arr[i].col; to[t]=p; while(i<=n&&arr[i].col==p) arr[i++].col=t; t++; } sort(arr+1, arr+n+1, [](rec a, rec b){return a.id<b.id;}); } long long gcd(long long a, long long b){ if(!a) return b; while(b) a%=b, swap(a, b); return a; } // 莫队 namespace mo{ que qs[100010]; int seq[200010], op[100010], ed[100010], ed2[100010], T, qpt, bk, bel[200010]; int cnt[100010], cnt2[100010]; long long sum[100010], sum2[100010]; bool ext[100010], u[200010]; void init(){ T=qpt=0; memset(cnt, 0, sizeof cnt); memset(sum, 0, sizeof sum); memset(cnt2, 0, sizeof cnt2); memset(sum2, 0, sizeof sum2); memset(ext, 0, sizeof ext); memset(u, 0, sizeof u); } // 处理询问 void prework(){ bk=ceil(sqrt(T)); for(int i=0, t=0;i<T;i+=bk, t++) for(int j=0;i+j<T&&j<bk;j++) bel[i+j]=t; for(int i=0;i<qpt;i++){ if(qs[i].lca){ if(qs[i].x==qs[i].y){ if(qs[i].a==1||qs[i].b==1) qs[i].ans=to[arr[qs[i].x].col]; else qs[i].ans=0; continue; } if(op[qs[i].x]>op[qs[i].y]) swap(qs[i].x, qs[i].y); if(qs[i].x==qs[i].lca) qs[i].l=op[qs[i].x]+1; else qs[i].l=ed[qs[i].x]; qs[i].r=op[qs[i].y]; } else qs[i].l=op[qs[i].x], qs[i].r=ed[qs[i].x]; } } void inc(int ss){ if(!u[ss]) return; int p=seq[ss]; sum2[cnt2[arr[p].col]++]-=to[arr[p].col]; sum2[cnt2[arr[p].col]]+=to[arr[p].col]; } void dec(int ss){ if(!u[ss]) return; int p=seq[ss]; sum2[cnt2[arr[p].col]--]-=to[arr[p].col]; sum2[cnt2[arr[p].col]]+=to[arr[p].col]; } void tog(int p){ if(ext[p]) sum[cnt[arr[p].col]--]-=to[arr[p].col], sum[cnt[arr[p].col]]+=to[arr[p].col]; else sum[cnt[arr[p].col]++]-=to[arr[p].col], sum[cnt[arr[p].col]]+=to[arr[p].col]; ext[p]^=1; } void go(){ prework(); sort(qs, qs+qpt, [](que a, que b){return bel[a.l]==bel[b.l]?a.r<b.r:bel[a.l]<bel[b.l];}); int l=0, r=0; ext[1]=1; sum[1]=sum2[1]=to[arr[1].col]; cnt[arr[1].col]=cnt2[arr[1].col]=1; for(int i=0;i<qpt;i++){ while(l<qs[i].l) tog(seq[l]), dec(l++); while(l>qs[i].l) tog(seq[--l]), inc(l); while(r<qs[i].r) tog(seq[++r]), inc(r); while(r>qs[i].r) tog(seq[r]), dec(r--); if(qs[i].lca){ if(qs[i].x==qs[i].y) continue; tog(qs[i].lca); qs[i].ans=gcd(sum[qs[i].a], sum[qs[i].b]); tog(qs[i].lca); } else qs[i].ans=gcd(sum2[qs[i].a], sum2[qs[i].b]); } sort(qs, qs+qpt, [](que a, que b){return a.id<b.id;}); } } namespace tree{ struct edge{ int to; edge *next; edge(int t, edge *n):to(t), next(n){} edge(){} }pool[200010], *g[100010]; int T, fa[100010], son[100010], siz[100010], top[100010], dep[100010]; void init(){ T=0; memset(son, 0, sizeof son); memset(g, 0, sizeof g); } void addedge(int u, int v){ g[u]=&(pool[T++]=edge(v, g[u])); g[v]=&(pool[T++]=edge(u, g[v])); } void dfs(int p){ siz[p]=1; mo::u[mo::T]=1; mo::seq[mo::op[p]=mo::T++]=p; for(edge *t=g[p];t;t=t->next){ if(t->to==fa[p]) continue; fa[t->to]=p; dep[t->to]=dep[p]+1; dfs(t->to); siz[p]+=siz[t->to]; if(siz[t->to]>siz[son[p]]) son[p]=t->to; } mo::seq[mo::ed[p]=mo::T++]=p; } void dfs2(int p, int t){ top[p]=t; if(son[p]) dfs2(son[p], t); for(edge *t=g[p];t;t=t->next){ if(t->to==fa[p]||t->to==son[p]) continue; dfs2(t->to, t->to); } } int lca(int u, int v){ while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]]) v=fa[top[v]]; else u=fa[top[u]]; } return dep[u]<dep[v]?u:v; } } // 处理询问 void rd(que &a){ a.lca=rd(); a.x=rd(), a.y=rd(); a.a=rd(), a.b=rd(); if(a.lca==1) a.lca=0; else a.lca=tree::lca(a.x, a.y); } int main(){ T=rd(); for(int r=1;r<=T;r++){ printf("Case #%d:\n", r); tree::init(); mo::init(); n=rd(), m=rd(); for(int i=1;i<=n;i++) arr[i].id=i, arr[i].col=rd(); lis(); for(int i=1;i<n;i++) tree::addedge(rd(), rd()); tree::dfs(1); tree::dfs2(1, 1); for(int i=0;i<m;i++) rd(mo::qs[mo::qpt]), mo::qs[mo::qpt++].id=i; mo::go(); for(int i=0;i<m;i++) printf("%lld\n", mo::qs[i].ans); } return 0; }希望多遇到良心出题人:) 不过也是自己菜。
