#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;
const int N=100009;
int n,m;
int a,b,c,x,y;
int len[N];
int get[N];
int vis[N],fa[N];
vector<pair<int,int> > v[N],need[N];
void dfs(int x,int f,int L)//处理出每个点到根的距离
{
vis[x]=1;
len[x]=L;
for(int i=0;i<v[x].size();i++)
{
int y=v[x][i].first;
if(y==f)continue;
dfs(y,x,L+v[x][i].second);
fa[y]=x;
}
}
void dfs2(int x,int f,int id)//vis[x]=id表示节点x对应环上的点id
{
vis[x]=id;
for(int i=0;i<v[x].size();i++)
{
int y=v[x][i].first;
if(y==f)continue;
dfs2(y,x,id);
}
}
void init()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
v[i].clear();
fa[i]=i;
vis[i]=0;
}
for(int i=1;i<=n-1;i++)
{
scanf("%d%d%d",&a,&b,&c);
v[a].push_back(make_pair(b,c));
v[b].push_back(make_pair(a,c));
}
scanf("%d%d%d",&a,&b,&c);
dfs(b,-1,0);//以b为根建树
fa[b]=-1;
if(c>=len[a])//如果加入的边比原先b-a的距离大,答案全为零
{
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
puts("0");
}
}
else
{
int x=a;
int id=3;
do //由a遍历到b,将非环上的点对应成环上的点
{
vis[x]=2;
for(int i=0;i<v[x].size();i++)
{
int y=v[x][i].first;
if(y==fa[x]||vis[y]==2)continue;
dfs2(y,x,id);
}
get[id]=x;//get[id]=x表示vis[y]=id的点都对应点x
id++;
x=fa[x];
}while(x!=-1);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
if(vis[x]!=2) x=get[vis[x]];//如果不是环上的点,找到对应点
if(vis[y]!=2) y=get[vis[y]];
if(len[y]<len[x]) swap(x,y);
int tmp1=len[y]-len[x];
int tmp2=len[x]+c+len[a]-len[y];//比较绕新加入的边是否可以减少距离
if(tmp2<tmp1)
{
printf("%d\n",tmp1-tmp2);
}
else
{
puts("0");
}
}
}
}
int main(){
int T;
scanf("%d",&T);
for(int ii=1;ii<=T;ii++)
{
printf("Case #%d:\n",ii);
init();
}
return 0;
}
分享到:
相关推荐
UESTC考研倒计时 可以记录考研倒计时
uestc图书馆联网利器。您是否为图书馆无法联网而苦恼过,快来下载吧
uestc 的清水河上网脚本,大家可以参考下怎么写shell,写的不错
一份UESTC的ACM题目推荐,可以当作入门题来切
微信小程序源码-Cheese-UESTC-master 校内新闻大图版小程序
uestc微处理器体系结构嵌入式系统设计 计算机系统组成与体系结构PPT教案.pptx
一个考研倒计时软件。。。 桌面上显示的,占用资源很小。。
uestc_os_exp:UESTC操作系统实验
图论及应用-uestc
UESTC 操作系统实验.zip
UESTC电子实验 大二下 复习PPT
uestc数字信号处理DSP答案 奥本海姆数字信号处理
电子科技大学研究生算法设计与分析课程的两次大作业和答案解析。目测肖明宇,董强老师的学生都管用
教学内容与要求 1掌握处理器在进程地址空间上的三种运行位置,了解内核编程不能使用C库函数和FPU,以及可能产生内存故障、核心栈溢出和四种内核竞争情形的原因。(2学时) 2熟悉进程描述符的组织,进程上下文和...
UESTC-计算机系统安全期末真题
UESTC矩阵随机复习资料.rar
uestc微机原理实验报告3.pdf
来自 UESTC ACM 的在线裁判核心分叉
UESTC专用,为了沙河的网络连接所传,希望可以对你们有帮助!