EZOJ #79
2024-10-21 13:35:07
分析
在经过若干次操作之后一定会产生一堆环
而我们又发现从一个点到另一个点实际可以经过所有环
于是问题就转换成了$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 ;
}
最新文章
- 自己动手写计算器v1.0
- MemCache 启动
- 图片加载完后执行js
- [转]Sql server2005中如何格式化时间日期
- jquery json ajax -2
- Image对象及其子类BufferedImage
- Sqoop导入mysql数据到Hbase
- How to recover after deleting the symbolic link libc.so.6?
- android开发之-Android 开发之4.0界面设计原则-整理
- 201521123031 《Java程序设计》第一周学习总结
- jsp页面取值
- ABP官方文档翻译 7.3 Quartz集成
- python[error] - mysql_config not found
- 如何使用Vue
- 恢复oracle中误删除drop掉的表 闪回的方法
- 20155219付颖卓《网络攻防》Exp4 恶意代码分析
- mysql中主键和唯一键的区别
- ubuntu 下关闭apache服务自动启动
- 检测Linux服务器端口是否开通
- PYQT5实现 关闭 提示弹框