2020-2021:teams:legal_string:jxm2001:contest:cf_feb21
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:contest:cf_feb21 [2021/02/16 19:40] jxm2001 |
2020-2021:teams:legal_string:jxm2001:contest:cf_feb21 [2021/02/16 19:42] (当前版本) jxm2001 [题解] |
||
|---|---|---|---|
| 行 309: | 行 309: | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <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> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/contest/cf_feb21.1613475626.txt.gz · 最后更改: 2021/02/16 19:40 由 jxm2001
