题意:给你n个城市,然后告诉你m条路,然后q个询问。第一个询问是让你输出该城市所在的区域的最长路。第二询问是让你把两个城市所在区域,并使得合并后的区域最长路最短。
条件:1 第二询问是要使得合并后的区域最长路最短
2 区域就是与该城市相连所有的城市构成的集合
思路:这题最难的地方在于求最开始最长路和使得合并后的区域最长路最短。求最开始的最长路可以采用两次dfs,dfs找到一个区域最长路,一个点对应最长路的终点,那个终点的最长路就是该区域的最长路。求合并后的区域最长路最短,两个区域合并最长路可以是原来两个区域的最长路,也可以是原先最长的要么是中点相连。
代码:
#include
#include
#include
#include
#include
using namespace std;
const int maxn=3*100000+5;//可以写成1e5
vectormp[maxn];//因为直接开数组会爆
int vis[maxn];//并查集
int s[maxn];//记录区域最大的路长
int father,lst,ans;
int getfather(int x)//找祖先
{if(vis[x]==x)return x;elsereturn vis[x]=getfather(vis[x]);
}
int dfs(int a,int pre,int step)//dfs找最大路
{vis[a]=father;//所有通路的祖先都是第一if(ans
总结:1 刚开始的时候看错题了,没有看到最长路的最小,英语有待提高
2 没有仔细得去找规律和思考










