8.9套题

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);
}