美团2023.4.8笔试

只整了两道：

1.第一题换座位

遍历座位

也就是统计右下方和左上方不同的数目，遇到边界取模。

代码没记录，忘。

2.给出一个树，选定树中一条边，求经过这条边的最长路径

输入：

第一行n，表示有n个节点。

第二行n-1个，表示p2,..pn，其中i与pi有连线

第三行a1,a2,表示这条边的两个节点

输出：

路径的长度

思路：

用vector数组建图，然后删除图中一条边，选定两个路径的两个端点分别dfs 记录最长路径len，相加得到答案

#include <bits/stdc++.h>
using namespace std;
int n,m,a;
int max1=-1;
void dfs(vector<int> tree[],int fat[],int i,int len){
    if(max1<len)max1=len;
    fat[i]=1;
    for(int no:tree[i]){
        if(fat[no]==0){
            dfs(tree,fat,no,len+1);
        }
    }
}
int main() {
    cin >> n;
    vector<int> tree[n + 5];
    int fat1[n+5];
    int vivid[n+5];
    for(int i=2;i<=n;i++){
        int no;
        cin >> no;
        tree[i].push_back(no);
        tree[no].push_back(i);
        fat1[i]=0;
    }
    fat1[1]=0;
    int u,v;
    cin >> u >> v;

    for(int i=0;i<tree[u].size();i++){
        if(tree[u][i]==v)tree[u].erase(tree[u].begin()+i);
    }

    for(int i=0;i<tree[v].size();i++){
        if(tree[v][i]==u)tree[v].erase(tree[v].begin()+i);
    }
    int res=0;

    dfs(tree,fat1,u,0);
    res+=max1+1;

    max1=0;
    dfs(tree,fat1,u,0);
    res+=max1;
    cout << res <<endl;
}