做国外贸易的网站,wordpress编辑用户头像,优秀高端网站建设报价,网站模板整站资源来源#xff1a;牛客网#xff1a; 文章目录题目描述题解#xff1a;代码#xff1a;时间限制#xff1a;C/C 3秒#xff0c;其他语言6秒
空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K
64bit IO Format: %lld题目描述 小A这次来到一个景区去旅游#xf…来源牛客网 文章目录题目描述题解代码时间限制C/C 3秒其他语言6秒
空间限制C/C 262144K其他语言524288K
64bit IO Format: %lld题目描述 小A这次来到一个景区去旅游景区里面有N个景点景点之间有N-1条路径。小A从当前的一个景点移动到下一个景点需要消耗一点的体力值。但是景区里面有两个景点比较特殊它们之间是可以直接坐观光缆车通过不需要消耗体力值。而小A不想走太多的路所以他希望你能够告诉它从当前的位置出发到他想要去的那个地方他最少要消耗的体力值是多少。 输入描述: 第一行一个整数N代表景区的个数。 接下来N-1行每行两个整数u,v代表从位置u到v之间有一条路径可以互相到达。 接下来的一行两个整数U,V表示这两个城市之间可以直接坐缆车到达。 接下来一行一个整数Q表示有Q次询问。 接下来的Q行每行两个整数x,y,代表小A的位置在x而他想要去的地方是y。 输出描述: 对于每个询问下x,y输出一个结果代表x到y消耗的最少体力对于每个询问下x,y输出一个结果代表x到y消耗的最少体力 示例1 输入 复制
4
1 2
1 3
2 4
3 4
2
1 3
3 4输出 复制
1
0备注: 1≤N≤3e5 1≤Q≤1e6
题解
如果没有缆车就是lca 但是有了缆车也不怕我们就考虑u,v从u到v是否需要坐缆车。假设缆车是(x,y),u到v远距离是disuv考虑缆车后就是看u是到x坐还是到y坐 disu,xdis(y,v)或dis(u,y)dis(x,v) 看哪个距离最近即可 (复习lca)
代码
#includebits/stdc.h
#define mp make_pair
#define se second
#define fi first
using namespace std;typedef long long ll;
//typedef pairint, int pii;
//typedef pairll, int pli;
//typedef pairll, ll pll;
typedef long double ld;const int N1e610;
const int MAXN20010;
const int INF0x3f3f3f3f;
const double eps0.0000001;
const ll mod998244353;
int head[N],to[N],nx[N],tot1;//n个点。n-1条边
int dep[N];
int sz[N];
int fa[N][32];
int n;
void add(int u,int v){to[tot]v;nx[tot]head[u];head[u]tot;
}
void dfs(int u,int f,int step){dep[u]step;fa[u][0]f;sz[u]1;for(int i1;i21;i){fa[u][i]fa[fa[u][i-1]][i-1];}for(int ihead[u];i;inx[i]){int vto[i];if(fv)continue;dfs(v,u,step1);sz[u]sz[v];}
}
int LCA(int u,int v){if(dep[u]dep[v])swap(u,v);int ddep[u]-dep[v];for(int i0;(1i)d;i){if((1i)d){ufa[u][i];}}if(uv)return u;for(int i21;i0;i--){if(fa[v][i]!fa[u][i]){vfa[v][i];ufa[u][i];}}return fa[u][0];
}
int main(){int n; scanf(%d,n);memset(head,-1,sizeof(head));for(int i 1; i n; i){int u,v;scanf(%d%d,u,v);add(u,v);add(v,u);}dfs(1,0,1);int a,b;scanf(%d%d,a,b);int q; scanf(%d,q);while(q--){int u, v;scanf(%d%d,u,v);int lca LCA(u,v);int ans dep[u] dep[v] - dep[lca]*2;int x LCA(u,a);int y LCA(b,v);ans min(ans,dep[u] dep[a] - dep[x]*2 dep[b] dep[v] - dep[y]*2);x LCA(u,b);y LCA(v,a);ans min(ans,dep[u] dep[b] - dep[x]*2 dep[a] dep[v] - dep[y]*2);printf(%d\n,ans);}return 0;
}
