GESP-C++八级 题库
手套配对
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有 n 对不同的手套,每对手套由左右各一只组成。
小杨想知道从中取出 m 只手套,m 只手套恰好包含 k 对手套的情况有多少种。
小杨认为两种取出的情况不同,当且仅当两种情况取出的手套中存在不同的手套(同一对手套的左右手也视为不同的手套)。
输入格式
第一行包含一个正整数 t ,代表测试用例组数。
接下来是 t 组测试用例。对于每组测试用例,一共一行。
第一行包含三个正整数n,m,k,代表手套数量,取出的手套数和目标对数。
输出格式
对于每组测试数据,输出一个整数,代表可能的情况数量对109+7 取模的结果。
输入样例
输出样例

对于全部数据,保证有1≤t≤105,1≤n≤1000,1≤m≤2×n,1≤k≤n。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3+10;
const int p = 1e9+7;
#define ll long long
ll c[N][N];
ll pw[N];
int n,m,k;
void init(){
pw[0]=1;
for(int i=0;i<N;i++){
if(i)pw[i]=pw[i-1]*2%p;
for(int j=0;j<=i;j++){
if(j==0)c[i][j]=1;
else c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
}
}
}
int main(){
init();
int t;
cin>>t;
while(t--){
cin>>n>>m>>k;
if(m<2*k||m-2*k>n-k){
cout<<"0\n";
continue;
}
ll ans=c[n][k]*c[n-k][m-2*k]%p;
ans=ans*pw[m-2*k]%p;
cout<<ans<<"\n";
}
}试题名称:美丽路径
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一棵包含 n 个节点的树,节点从 1 到 n 编号,并且每个节点要么是白色,要么是黑色。
对于树上的一条简单路径(不经过重复节点的路径),小杨认为它是美丽的当且仅当路径上相邻节点的颜色均不相同。例如下图,其中节点 1 和节点 4 是黑色,其余节点是白色,路径2−1−3−4 是美丽路径,而 路径2−1−3−5 不是美丽路径(相邻节点 3 和 5 颜色相同)。

对于树上的一条简单路径,小杨认为它的长度是路径包含节点的数量。小杨想知道最长的美丽路径的长度是多少。
输入格式
第一行包含一个正整数 n ,代表节点数量。
第二行包含 n 个整数c1,c2,...,cn,代表每个节点的颜色,如果 ci=0,代表节点 i 为白色,如果ci=1,代表节点 i 为黑色。
之后 n−1 行,每行包含两个正整数ui,vi,代表存在一条连接节点ui和节点vi的边。
输出格式
输出一个整数,代表最长美丽路径的长度。
输入样例1
输出样例1
输入样例2
输出样例

对于全部数据,保证有1≤n≤105,0≤ci≤1,同时保证给出的数据构成一棵树。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
vector<int> g[N];
int dep[N],vis[N],c[N];
int n,ans;
int dfs(int x,int fa){
vis[x]=1;
dep[x]=dep[fa]+1;
int mx = dep[x];
vector<int> tmp;
tmp.push_back(mx);
for(auto i:g[x]){
if(i==fa||c[i]==c[x])continue;
int d = dfs(i,x);
tmp.push_back(d);
mx = max(d,mx);
}
sort(tmp.begin(),tmp.end());
int m = tmp.size(),res=1;
if(m>1){
res = tmp[m - 1] + tmp[m - 2] - 2 * dep[x] + 1;
}
ans=max(ans,res);
return mx;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>c[i];
}
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1;i<=n;i++){
if(!vis[i]){
dfs(i,0);
}
}
cout<<ans<<"\n";
}1.定义DP[x][0/1]:x以x为根的,x颜色为(0白1黑)的最长链路节点数量
初始化:DP[x][A[x]]=1 ,DP[x][1-A[x]]=0;
2.定义Fx:穿过x的满足题目要求的最长节点数量,则Fx由以x为端点的最长链和次长链组成。
状态转移方程:
对(父亲x->孩子y A[x]为x的节点颜色)
①若A[x]=0:DP[x][0]=max(DP[x][0],DP[y][1]+1);
②若A[x]=1:DP[x][1]=max(DP[x][1],DP[y][0]+1);
在此基础上,Fx因为由最长和次长组成,因此需要在DP[x]更新前完成更新,因此:
①若A[x]=0
Fx=max(Fx,DP[x][0]+DP[y][1]);
DP[x][0]=max(DP[x][0],DP[y][1]+1);
②若A[x]=1;
Fx=max(Fx,DP[x][1]+DP[y][0]);
DP[x][1]=max(DP[x][1],DP[y][0]+1);
目标状态:Fx
最远点对
题面描述
小杨有一棵包含n个节点的树,这棵树上的任意一个节点要么是白色,要么是黑色。
小杨想知道相距最远的一对不同颜色节点的距离是多少。
输入格式
第一行包含一个正整数 n,代表树的节点数。
第二行包含n个非负整数a1,a2,...,an(对于所有的1≤i≤n,均有ai等于0或1),其中如果ai=0,则节点i的颜色为白色;如果ai=1,则节点i的颜色为黑色。
之后n-1行,每行包含两个正整数xi,yi,代表存在一条连接节点xi和yi的边。
保证输入的树中存在不同颜色的点。
输出格式
输出一个整数,代表相距最远的一对不同颜色节点的距离。
输入样例
输出样例
样例解释
相距最远的不同颜色的一对节点为节点 2 和 5。
数据范围

对于全部数据,保证有1≤n≤105,0≤ai≤1。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
vector<int> g[N];
int col[N];
int n;
int dep[N],far[N][2];
int ans;
void dfs(int x,int fa){
dep[x]=dep[fa]+1;
far[x][col[x]]=dep[x];
for(int i:g[x]){
if(i!=fa){
dfs(i,x);
for(int j=0;j<2;j++){
if(far[x][j]!=-1&&far[i][j^1]!=-1){
ans = max(ans,far[x][j]-dep[x]+far[i][j^1]-dep[x]);
}
}
for(int j=0;j<2;j++){
far[x][j]=max(far[x][j],far[i][j]);
}
}
}
ans = max(ans,far[x][col[x]^1]-dep[x]);
}
int main(){
int n;
cin>>n;
memset(far,-1,sizeof far);
for(int i=1;i<=n;i++){
cin>>col[i];
}
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
cout<<ans<<"\n";
}每个结点要么黑色要么白色,需要保存结点的颜色信息。选2个颜色不同的点,可以先枚举第1个点和第2个点,求他们的距离,再求最大值。任意2点都是连通的,能够相互访问,能求出最大值。根据数据范围,能得到部分分。另一种思路就是根据树的性质,答案的2个点假设是a和b,路径会经过他们的公共祖先,距离=公共祖先到a的距离+公共祖先到b的距离。每个点视为公共祖先的话,有可能是左孩子的黑色和右孩子的白色组合,也可能是左孩子的白色和右孩子的黑色组成,也可能只在左孩子或者右孩子中。所以,每个结点应该保留2种颜色的最远值。一次深搜即可。每个点访问1次,时间复杂度是O(n)。
空间跳跃
题面描述
小杨在二维空间中有n个水平挡板,并且挡板之间彼此不重叠,其中第i个挡板处于水平高度hi,左右端点分别位于li 与 ri。
小杨可以在挡板上左右移动,当小杨移动到右端点时,如果再向右移动会竖直掉落,从而落到下方第一个挡板上,移动到左端点时同理。小杨在挡板上每移动1个单位长度会耗费 1个单位时间,掉落时每掉落1 个单位高度也会耗费 1个单位时间。
小杨想知道,从第 s个挡板上的左端点出发到第t个挡板需要耗费的最少时间是多少?
注意:可能无法从第 s个挡板到达到第 t个挡板。
输入格式
第一行包含一个正整数n ,代表挡板数量。
第二行包含两个正整数s,t ,含义如题面所示。
之后 n行,每行包含三个正整数li,ri,hi ,代表第 i个挡板的左右端点位置与高度。
输出格式
输出一个整数代表需要耗费的最少时间,如果无法到达则输出 -1。
输入样例
输出样例
样例范围
耗费时间最少的移动方案为,从第3个挡板左端点移动到右端点,耗费3个单位时间,然后向右移动掉落到第 2个挡板上,耗费 100000-6=99994个单位时间,之后再向右移动1个单位长度,耗费1个单位时间,最后向右移动掉落到第1个挡板上,耗费3个单位时间。共耗费 3+99994+1+3=100001个单位时间。
数据范围

对于全部数据,保证有1≤n≤1000,1≤li≤ri≤105,1≤hi≤105。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
struct edge {
int v, w;
edge() {
}
edge(int vv,int ww) {
v=vv;
w=ww;
}
};
struct node {
int dis, u;
node () {
}
node (int diss,int uu) {
dis=diss;
u=uu;
}
bool operator>(const node& a) const {
return dis > a.dis;
}
};
vector<edge> e[maxn];
int dis[maxn], vis[maxn];
priority_queue<node, vector<node>, greater<node> > q;
int cnt;
void dijkstra(int s) {
for (int i=1;i<=cnt;i++)dis[i]=INT_MAX;
dis[s] = 0;
q.push(node(0, s));
while (!q.empty()) {
int u = q.top().u;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto ed : e[u]) {
int v = ed.v, w = ed.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push(node(dis[v], v));
}
}
}
}
map<pair<int,int>,int> mp;
vector<int> es[2010];
int l[maxn],r[maxn],h[maxn];
int main() {
int n;
cin>>n;
int s,t;
cin>>s>>t;
for (int i=1;i<=n;i++) {
cin>>l[i]>>r[i]>>h[i];
mp[make_pair(l[i],h[i])]=i;
mp[make_pair(r[i],h[i])]=n+i;
es[i].push_back(i);
es[i].push_back(n+i);
e[i].push_back(edge(n+i,r[i]-l[i]));
e[n+i].push_back(edge(i,r[i]-l[i]));
}
cnt=2*n+1;
for (int i=1;i<=n;i++) {
int hh = -1,idx = i;
for (int j=1;j<=n;j++) {
if(i==j)continue;
if(l[j]<=l[i]&&l[i]<=r[j]&&h[j]<=h[i]) {
if(h[j]>hh) {
hh=h[j];
idx=j;
}
}
}
if(hh!=-1) {
if(!mp[make_pair(l[i],hh)]) {
mp[make_pair(l[i],hh)]=cnt++;
}
int v = mp[make_pair(l[i],hh)];
e[i].push_back(edge(v,h[i]-hh));
e[idx].push_back(edge(v,abs(l[i]-l[idx])));
e[n+idx].push_back(edge(v,abs(l[i]-r[idx])));
e[v].push_back(edge(idx,abs(l[i]-l[idx])));
e[v].push_back(edge(n+idx,abs(l[i]-r[idx])));
es[idx].push_back(v);
}
hh = -1,idx = i;
for (int j=1;j<=n;j++) {
if(i==j)continue;
if(l[j]<=r[i]&&r[i]<=r[j]&&h[j]<=h[i]) {
if(h[j]>hh) {
hh=h[j];
idx=j;
}
}
}
if(hh!=-1) {
if(!mp[make_pair(r[i],hh)]) {
mp[make_pair(r[i],hh)]=cnt++;
}
int v = mp[make_pair(r[i],hh)];
e[n+i].push_back(edge(v,h[i]-hh));
e[idx].push_back(edge(v,abs(r[i]-l[idx])));
e[n+idx].push_back(edge(v,abs(r[i]-r[idx])));
e[v].push_back(edge(idx,abs(r[i]-l[idx])));
e[v].push_back(edge(n+idx,abs(r[i]-r[idx])));
es[idx].push_back(v);
}
}
dijkstra(s);
int ans = INT_MAX;
for (auto i:es[t]) {
ans=min(ans,dis[i]);
}
if(ans!=INT_MAX)cout<<ans<<"\n"; else cout<<"-1\n";
}发现n的数据范围是1000,求的是从1个挡板到另外1个挡板。注意,掉到目标挡板中的某个位置即可。同时1个挡板左端到右端或者右端到左端算距离,其他挡板的2个端点只要能垂直相交到下一个挡板(中间没有其他挡板阻碍),也算相连。将这些端点和相交点看成结点,相连看成边,整个结构就成为一张图的结构。起点是固定的,终点也是固定的(只要是目标挡板的某个点即可),求的就是最短路径。数据都是正整数,可以用dijkstra算法实现。
难点1在于建图。一个挡板左右算2个结点,要连边;一个挡板的左右两端能够垂直到其他挡板,中间不能有间隔,要连边。
难度2就是dijkstra算法的完成。按照优先队列的模板完成即可。
公倍数问题
问题描述
小 A 写了一个N×M的矩阵A,我们看不到这个矩阵,但我们可以知道,其中第i行第j列的元素Aij是i和j的公倍数(i=1,...,N,j=1,...,M)。现在有K个小朋友,其中第k个小朋友想知道,矩阵A中最多有多少个元素可以是k(k=1,2,...,K)。请你帮助这些小朋友求解。
注意:每位小朋友的答案互不相关,例如,有些位置既可能是x,又可能是y,则它同可以时满足x,y两名小朋友的要求。
方便起见,你只需要输出
即可,其中ansk表示第k名小朋友感兴趣的答案。
输入描述
第一行三个正整数N,M,K。
输出描述
输出一行,即
。
请注意,这个数可能很大,使用 C++ 语言的选手请酌情使用 long long 等数据类型存储答案。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出 1
样例解释 1
只有A1,1可以是1,其余都不行。
A1,1,A1,2,A2,1,A2,2都可以是2,而其余不行。
因此答案是1×1+2×4=9。
样例输入 2
样例输出 2
数据规模
对于30的测试点,保证N,M,K≤10;
对于60的测试点,保证N,M,K≤500;
对于100的测试点,保证N,M≤105,K≤106。
#include <iostream>
#include <vector>
using namespace std;
vector<int> count_divisors(int limit, int num) {
vector<int> s(num + 1, 0);
for (int i = 1; i <= limit; ++i) {
for (int j = i; j <= num; j += i) {
s[j] += 1;
}
}
return s;
}
int main() {
int N, M, K;
cin >> N >> M >> K;
vector<int> s_N = count_divisors(N, 1000000);
vector<int> s_M = count_divisors(M, 1000000);
long long result = 0;
for (int k = 1; k <= K; ++k) {
result += (long long)k * s_N[k] * s_M[k];
}
cout << result << endl;
return 0;
}接竹竿
题面描述
小杨同学想用卡牌玩一种叫做“接竹竿”的游戏。
游戏规则是:每张牌上有一个点数v,将给定的牌依次放入一列牌的末端。若放入之前这列牌中已有与这张牌点数相同的牌,则小杨同学会将这张牌和点数相同的牌之间的所有牌全部取出队列(包括这两张牌本身)。
小杨同学现在有一个长度为n的卡牌序列A,其中每张牌的点数为Ai(1≤i≤n)。小杨同学有q次询问。第i次(1≤i≤q)询问时,小杨同学会给出li,ri,小杨同学想知道如果用下标在[li,ri]的所有卡牌按照下标顺序玩“接竹竿”的游戏,最后队列中剩余的牌数。
输入格式
第一行包含一个正整数T,表示测试数据组数。
对于每组测试数据,第一行包含一个正整数n,表示卡牌序列A的长度。
第二行包含n个正整数A1,A2,...An,,表示卡牌的点数A。
第三行包含一个正整数q,表示询问次数。
接下来q行,每行两个正整数li,ri,表示一组询问。
输出格式
对于每组数据,输出q行。第i行(1≤i≤q)输出一个非负整数,表示第i次询问的答案。
样例输入
样例输入
样例解释
对于第一次询问,小杨同学会按照1,2,2的顺序放置卡牌,在放置最后一张卡牌时,两张点数为2的卡牌会被收走,因此最后队列中只剩余一张点数为1的卡牌。
对于第二次询问,队列变化情况为:
{}→{1}→{1,2}→{1,2,2}→{1}→{1,3}→{1,3,1}→{}→{3}。因此最后队列中只剩余一张点数为3的卡牌。
数据范围

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10;
int a[N];
int nxt[N][30],pos[20];
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
memset(pos,0,sizeof pos);
for(int i=1;i<=n;i++){
cin>>a[i];
for(int j=0;j<=20;j++)nxt[i][j]=n+1;
}
for(int i=n;i>=1;i--){
if(!pos[a[i]]){
nxt[a[i]][0]=n+1;
pos[a[i]]=i;
}else{
nxt[i][0]=pos[a[i]];
pos[a[i]]=i;
}
}
for(int i=n;i>=1;i--){
for(int j=1;j<=20;j++){
if(nxt[i][j-1]+1<=n)
nxt[i][j]=nxt[nxt[i][j-1]+1][j-1];
}
}
int q;
cin>>q;
while(q--){
int l,r;
cin>>l>>r;
int ii=l;
int ans=0;
while(ii<=r){
while(ii<=r&&nxt[ii][0]>r){
ii++;
ans++;
}
if(ii>r)break;
for(int j=20;j>=0;j--){
if(nxt[ii][j]<=r){
ii=nxt[ii][j];
break;
}
}
ii++;
}
cout<<ans<<"\n";
}
}
}奖品分配
时间限制:1.0 s
内存限制:128.0 MB
问题描述
班上有N名同学,学号从0到N-1。有 种奖品要分给这些同学,其中,第M种奖品总共有ai个(i=0,1,…,M-1)。巧合的是,奖品的数量不多不少,每位同学都可以恰好分到一个奖品,且最后剩余的奖品不超过1个(即:N≤a0+a1+…+aM-1≤N+1)。
现在,请你求出每个班级礼物分配的方案数,所谓方案,指的是为每位同学都分配一个种类的奖品。只要有一位同学获得了不同种类的奖品,即视为不同的方案。方便起见,你只需要输出方案数对109+7取模后的结果即可。
共有T个班级都面临着奖品分配的问题,你需要依次为他们解答。
输入描述
第一行一个整数T,表示班级数量。
接下来 行,每行若干用单个空格隔开的正整数。首先是两个正整数N,M,接着是M个正整数a0,a1,…,aM-1。
保证N≤a0+a1+…+aM-1≤N+1。
输出描述
输出T行,每行一个整数,表示该班级分配奖品的方案数对109+7取模的结果。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出 1
样例解释 1
对于第 1 个班级,学号为0,1,2的同学可以依次分别获得奖品0,1,1,也可以依次分别获得奖品1,0,1,也可以依次分别获得奖品1,1,0,因此共有3种方案。
对于第 2 个班级,学号为0,1,2的同学可以依次分别获得奖品0,1,1,也可以依次分别获得奖品1,0,1,也可以依次分别获得奖品1,1,0,也可以依次分别获得奖品1,1,1,因此共有4种方案。
对于第 3 个班级,可以把编号为1的奖品分配给5名同学中的任意一名,共有5种方案;再把编号为2的奖品分配给剩余4名同学中的任意一名,共有4种方案;最后给剩余3名同学自然获得0号奖品。因此,方案数为5×4=20。
样例输入 2
样例输出 2
数据规模
对于30%的测试点,保证N≤10。
对于另外30%的测试点,保证M=2。
对于所有测试点,保证N≤1000;保证T≤1000;保证M≤1000。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
const int N = 1005;
const int mod = 1e9 + 7;
int C[N + 5][N + 5], a[N + 5];
void add(int &a, int b) {
a += b;
if (a >= mod)
a -= mod;
}
void init() {
C[0][0] = 1;
for (int i = 1; i <= N; i++) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++)
C[i][j] = C[i - 1][j - 1], add(C[i][j], C[i - 1][j]);
}
}
int main() {
// freopen("data/10.in", "r", stdin);
init();
int T;
scanf("%d", &T);
while (T--) {
int n, m, sum = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
scanf("%d", &a[i]), sum += a[i];
int ans = 1;
for (int i = 1; i <= m; i++) {
ans = 1ll * ans * C[sum][a[i]] % mod;
sum -= a[i];
}
cout << ans << endl;
}
return 0;
}大量的工作沟通
时间限制:2.0 s
内存限制:128.0 MB
问题描述
某公司有N名员工,编号从0至N-1。其中,除了0号员工是老板,其余每名员工都有一个直接领导。我们假设编号为i的员工的直接领导是fi。
该公司有严格的管理制度,每位员工只能受到本人或直接领导或间接领导的管理。具体来说,规定员工x可以管理员工y,当且仅当x=y,或f=fy,或x可以管理fy。特别地,0号员工老板只能自我管理,无法由其他任何员工管理。
现在,有一些同事要开展合作,他们希望找到一位同事来主持这场合作,这位同事必须能够管理参与合作的所有同事。如果有多名满足这一条件的员工,他们希望找到编号最大的员工。你能帮帮他们吗?
输入描述
第一行一个整数N,表示员工的数量。
第二行N-1个用空格隔开的正整数,依次为f1,f2…,fN-1。
第三行一个整数Q,表示共有Q场合作需要安排。
接下来Q行,每行描述一场合作:开头是一个整数m(2≤m≤N),表示参与本次合作的员工数量;接着是m个整数,依次表示参与本次合作的员工编号(保证编号合法且不重复)。
保证公司结构合法,即不存在任意一名员工,其本人是自己的直接或间接领导。
输出描述
输出Q行,每行一个整数,依次为每场合作的主持人选。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出 1
样例解释 1
对于第一场合作,员工3,4有共同领导2,可以主持合作。
对于第二场合作,员工2本人即可以管理所有参与者。
对于第三场合作,只有0号老板才能管理所有员工。
样例输入 2
样例输出 2
数据规模
对于25%的测试点,保证N≤50。
对于50%的测试点,保证N≤300。
对于所有测试点,保证3≤N≤105;保证Q≤100,保证m≤104。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
using namespace std;
const int N = 100005;
int fa[N], sz[N], dep[N], son[N], tp[N], mxId[N];
int cnt, fir[N], tar[N], nxt[N];
void link(int a, int b) { tar[++cnt] = b, nxt[cnt] = fir[a], fir[a] = cnt; }
void dfs(int x, int mxid) {
int Mx = 0;
sz[x] = 1;
mxId[x] = max(x, mxid);
for (int i = fir[x]; i; i = nxt[i]) {
dep[tar[i]] = dep[x] + 1;
dfs(tar[i], mxId[x]);
sz[x] += sz[tar[i]];
if (Mx < sz[tar[i]])
Mx = sz[son[x] = tar[i]];
}
}
void gettp(int x) {
tp[x] = x;
if (son[fa[x]] == x)
tp[x] = tp[fa[x]];
for (int i = fir[x]; i; i = nxt[i])
gettp(tar[i]);
}
int lca(int x, int y) {
while (tp[x] != tp[y])
dep[tp[x]] > dep[tp[y]] ? x = fa[tp[x]] : y = fa[tp[y]];
return dep[x] < dep[y] ? x : y;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 2; i <= n; i++)
scanf("%d", &fa[i]), link(++fa[i], i);
dfs(1, 1), gettp(1);
int q;
scanf("%d", &q);
while (q--) {
int m, x, y;
scanf("%d%d", &m, &x), x++;
for (int i = 2; i <= m; i++)
scanf("%d", &y), x = lca(x, ++y);
cout << mxId[x] - 1 << endl;
}
return 0;
}消息查找


#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
const int C = 2e3 + 5;
const int oo = 1e9;
int n, q;
int r[N], mark[N], pos[N];
int p[C], cnt;
int d[C][C];
int pre[N], suf[N];
int main()
{
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++)
{
scanf("%d", &r[i]);
if (r[i])
mark[i] = mark[r[i]] = 1;
}
for (int i = 1; i <= n; i++)
{
if (mark[i])
{
p[++cnt] = i;
pos[i] = cnt;
}
}
for (int i = 1; i <= cnt; i++)
{
for (int j = 1; j <= i; j++)
d[i][j] = oo;
d[i][i] = 0;
for (int j = i; j > 1; j--)
{
d[i][j - 1] = min(d[i][j - 1], d[i][j] + p[j] - p[j - 1]);
if (r[p[j]])
{
int k = pos[r[p[j]]];
d[i][k] = min(d[i][k], d[i][j] + 1);
}
}
}
for (int i = 1; i <= n; i++)
{
pre[i] = pre[i - 1];
if (mark[i])
pre[i] = i;
}
suf[n + 1] = n + 1;
for (int i = n; i; i--)
{
suf[i] = suf[i + 1];
if (mark[i])
suf[i] = i;
}
while (q--)
{
int x, y;
scanf("%d%d", &x, &y);
if (pre[x] < suf[y])
{
printf("%d\n", x - y);
}
else
{
printf("%d\n", x - pre[x] + d[pos[pre[x]]][pos[suf[y]]] + suf[y] - y);
}
}
return 0;
}子图最短路


#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 105;
const int mod = 1e9;
int n, m;
int f[N][N];
int g[N][N];
int ans;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
f[i][j] = mod;
f[i][i] = 0;
}
for (int i = 1; i <= m; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
f[u][v] = min(f[u][v], w);
f[v][u] = min(f[v][u], w);
}
for (int l = 1; l <= n; l++)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
g[i][j] = f[i][j];
for (int r = l; r <= n; r++)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
g[i][j] = min(g[i][j], g[i][r] + g[r][j]);
for (int i = l; i <= r; i++)
for (int j = i; j <= r; j++)
ans = (ans + g[i][j]) % mod;
}
}
printf("%d\n", ans);
return 0;
}