2020-2021:teams:legal_string:jxm2001:contest:cf_feb21
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:contest:cf_feb21 [2021/02/16 12:25] jxm2001 [题解 1] |
2020-2021:teams:legal_string:jxm2001:contest:cf_feb21 [2021/02/16 19:42] (当前版本) jxm2001 [题解] |
||
|---|---|---|---|
| 行 276: | 行 276: | ||
| 可以 $O(n\log v)$ 得到答案，具体见该[[https://www.codechef.com/viewsolution/42840665|代码]] | 可以 $O(n\log v)$ 得到答案，具体见该[[https://www.codechef.com/viewsolution/42840665|代码]] | ||
| + | |||
| + | ===== Another Tree with Number Theory ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定一棵以 $1$ 为根的树，接下来 $q$ 次询问。 | ||
| + | |||
| + | 每次询问给定一个结点 $u$ 初始权值 $w$。当结点 $u$ 拥有权值 $w$ 时，如果结点 $u$ 是叶子结点，则该权值被吸收。 | ||
| + | |||
| + | 否则记 $u$ 的儿子结点数为 $k$。若 $k\mid w$，则结点 $u$ 将权值均分为 $k$ 份并转移到每个儿子结点并继续下传，否则该权值损失。 | ||
| + | |||
| + | 问每次损失的权值。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 首先如果某个结点只有一个儿子，则将该结点与其儿子合并。 | ||
| + | |||
| + | 对结点 $u$，设他到某个叶子结点的路径上所有点的儿子结点数的乘积为 $k$。若 $k\mid w$，则该叶子结点能吸收权值 $\frac wk$，否则无法吸收。 | ||
| + | |||
| + | 考虑对每个结点用 $\text{map}$ 维护他每个 $k$ 对应的叶子节点数。 | ||
| + | |||
| + | 由于每次向上一级 $k$ 至少乘以 $2$，于是一个叶子结点最多对 $O(\log w)$ 个祖先节点有贡献。故维护 $\text{map}$ 的时间复杂度为 $O\left(n\log w\log n\right)$。 | ||
| + | |||
| + | 对每个询问，用其存储在权值对应的桶中，然后跑一遍埃氏筛枚举因子计算贡献。 | ||
| + | |||
| + | 总时间复杂度 $O(n\log n\log w+w\log w+q\times \text{divisors}(w)\log n)$。 | ||
| + | |||
| + | 如果用哈希表替代 $\text{map}$，时间复杂度为 $(n\log w+w\log w+q\times \text{divisors}(w))$。 | ||
| + | |||
| + | ps. $\text{map}$ 访问空建默认返回 $0$ 但非常慢，不建议利用该特性，推荐用 $\text{find}$ 特判后再访问。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e5+5,MAXW=1e6+5; | ||
| + | struct Edge{ | ||
| + | int to,next; | ||
| + | }edge[MAXN]; | ||
| + | int head[MAXN],edge_cnt; | ||
| + | void Insert(int u,int v){ | ||
| + | edge[++edge_cnt]=Edge{v,head[u]}; | ||
| + | head[u]=edge_cnt; | ||
| + | } | ||
| + | int idx[MAXN],ch[MAXN],ans[MAXN]; | ||
| + | map<int,int> d[MAXN]; | ||
| + | vector<pair<int,int> > query[MAXW]; | ||
| + | void dfs(int u){ | ||
| + | if(!ch[u]){ | ||
| + | d[u][1]=1; | ||
| + | return; | ||
| + | } | ||
| + | for(int i=head[u];i;i=edge[i].next){ | ||
| + | int v=edge[i].to; | ||
| + | dfs(v); | ||
| + | if(ch[u]==1){ | ||
| + | idx[u]=idx[v]; | ||
| + | return; | ||
| + | } | ||
| + | v=idx[v]; | ||
| + | for(map<int,int>::iterator it=d[v].begin();it!=d[v].end();++it){ | ||
| + | LL k=1LL*ch[u]*it->first; | ||
| + | if(k<MAXW) | ||
| + | d[u][k]+=it->second; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(); | ||
| + | _rep(i,1,n)idx[i]=i; | ||
| + | _rep(i,2,n){ | ||
| + | int p=read_int(); | ||
| + | ch[p]++; | ||
| + | Insert(p,i); | ||
| + | } | ||
| + | dfs(1); | ||
| + | int q=read_int(); | ||
| + | _for(i,0,q){ | ||
| + | int v=read_int(),w=read_int(); | ||
| + | ans[i]=w; | ||
| + | query[w].push_back(make_pair(i,idx[v])); | ||
| + | } | ||
| + | _for(i,1,MAXW){ | ||
| + | for(int j=i;j<MAXW;j+=i){ | ||
| + | _for(k,0,query[j].size()){ | ||
| + | int u=query[j][k].second; | ||
| + | if(d[u].find(i)!=d[u].end()) | ||
| + | ans[query[j][k].first]-=j/i*d[u][i]; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | _for(i,0,q) | ||
| + | enter(ans[i]); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/contest/cf_feb21.1613449507.txt.gz · 最后更改: 2021/02/16 12:25 由 jxm2001
