传送门

分析

在经过若干次操作之后一定会产生一堆环

而我们又发现从一个点到另一个点实际可以经过所有环

于是问题就转换成了$k_1s_1 + k_2s_2 + ... + len = t$

其中$s_i$为每个环的长度,$len$为两点间距离

于是每次gcd求一下就行了

注意两点间距离不用求LCA,用深度值减一下就可以了

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
long long d[];
vector<pair<int,int> >v[];
inline void dfs(int x,int fa){
long long i,j,k;
for(i=;i<v[x].size();i++){
int y=v[x][i].first,z=v[x][i].second;
if(y==fa)continue;
d[y]=d[x]+z;
dfs(y,x);
}
return;
}
inline long long gcd(long long x,long long y){return y==?x:gcd(y,x%y);}
int main(){
int n,m,i,j,k;
long long res=-;
scanf("%d%d",&n,&m);
for(i=;i<n;i++){
int x,y;
int z;
scanf("%d%d%d",&x,&y,&z);
v[x].push_back(make_pair(y,z));
v[y].push_back(make_pair(x,-z));
}
d[]=;
dfs(,);
for(i=;i<=m;i++){
int x,y;
int z;
scanf("%d",&k);
scanf("%d%d%d",&x,&y,&z);
if(k==){
long long t=d[x]-d[y]+z;
if(res==-){
res=abs(t);
}else {
res=gcd(res,abs(t));
}
}else {
long long t=d[y]-d[x]-z;
if(res!=-){
if(abs(t)%res==)puts("yes");
else puts("no");
}else {
if(t==)puts("yes");
else puts("no");
}
}
}
return ;
}

最新文章

  1. 自己动手写计算器v1.0
  2. MemCache 启动
  3. 图片加载完后执行js
  4. [转]Sql server2005中如何格式化时间日期
  5. jquery json ajax -2
  6. Image对象及其子类BufferedImage
  7. Sqoop导入mysql数据到Hbase
  8. How to recover after deleting the symbolic link libc.so.6?
  9. android开发之-Android 开发之4.0界面设计原则-整理
  10. 201521123031 《Java程序设计》第一周学习总结
  11. jsp页面取值
  12. ABP官方文档翻译 7.3 Quartz集成
  13. python[error] - mysql_config not found
  14. 如何使用Vue
  15. 恢复oracle中误删除drop掉的表 闪回的方法
  16. 20155219付颖卓《网络攻防》Exp4 恶意代码分析
  17. mysql中主键和唯一键的区别
  18. ubuntu 下关闭apache服务自动启动
  19. 检测Linux服务器端口是否开通
  20. PYQT5实现 关闭 提示弹框

热门文章

  1. hive_学习_00_资源帖
  2. 条款50:使用自定义的new以及delete的时机会
  3. IDEA Tomcat服务器 更新.jsp时,页面刷新无法同步修改
  4. Js中获取键盘的事件
  5. CentOS6.5下安装mongodb
  6. Python数据库(二)-Mysql数据库插入数据
  7. python正则以及collections模块
  8. 使用AJAX异步提交表单的几种方式
  9. DAY17-Django之logging
  10. java在Win7 64位 获取客户端的IP,MAC,计算机名