A. 猴猴吃苹果
题意:给定根节点k,求访问点的顺序,使得每次从上一个点到当前点的权值最大。访问过的点权值为0。权值一样时,输出最小编号
思路:由于是双向边,先求根节点到每一个节点的距离值。在第一轮中,最深的叶节点一定为答案,那么这一条路径就被访问过了,权值变为0,这个叶节点相同路径上的其他点到根节点(最后一个未被标记的点)的权值就改变了。所以从最优的叶节点出发,dfs往上跳,直到访问到已经被访问过的点为止即可。最后排序更新后的权值
#include<bits/stdc++.h>using namespace std;const int N = 1e6 + 10;int n,k,d[N],tot;
bool vis[N];
struct node{int id,val;
}a[N];
vector<int> v[N];
inline bool cmp(node p,node q){if(p.val!=q.val) return p.val>q.val;else return p.id<q.id;
}
void dfs1(int p,int fa){for(int t:v[p]){if(t==fa) continue;d[t]=d[p]+1;dfs1(t,p);}
}
void dfs2(int p,int fa){if(vis[p]) return;tot++;vis[p]=true;for(int t:v[p]){if(t==fa||d[t]>=d[p]) continue;dfs2(t,p);}
}
int main(){cin>>n>>k;for(int i=1,x;i<n;i++){cin>>x;v[i].push_back(x);v[x].push_back(i);}dfs1(k,-1);vis[k]=true;for(int i=0;i<n;i++){a[i].id=i;a[i].val=d[i];}sort(a,a+n,cmp);
// for(int i=0;i<n;i++) cout<<a[i].id<<" ";for(int i=0;i<n;i++){tot=0;dfs2(a[i].id,-1);a[i].val=tot;
// cout<<tot<<" "<<a[i].id<<endl;}sort(a,a+n,cmp);cout<<k<<endl;for(int i=0;i<n;i++){if(a[i].val)cout<<a[i].id<<endl;}return 0;
}
B. 猴猴吃香蕉
题意:选取n个数中的若干个数,使得它们的乘积为k
思路:计数dp,容易得出的转移方程式。使得为组成k的一个因子。由于k的范围不可接受,于是筛出k的所有因子,如果能整除,说明这个数能被分解。,由于因子较大,且个数趋近根号n,需要离散化
最终dp方程:,答案为
C. 猴猴的比赛
题意:给定两棵树,求一个节点x在两棵树中有相同祖先的对数
思路:考虑求出每一个点的子树中的范围(连续的),对于另一颗树而言,每次处理一个点答案计数完成后,就将这个点在第一棵树中的位置标记为1。答案计数为所有父节点中1的数量。注意在遍历子节点时,需要减去子树所有点的中1的数量,防止重复运算
核心代码:
void dfs2(int p,int fa){//L[p]为点p的dfn序for(int t:g[p]){if(t==fa) continue;ans-=BIT.query(R[t])-BIT.query(L[t]);dfs2(t,p);} ans+=BIT.query(R[p])-BIT.query(L[p]);//整个子树 BIT.add(L[p],1);
}