[题目链接]

https://www.lydsy.com/JudgeOnline/problem.php?id=1316

[算法]

点分治

由于边权较大,笔者在计算时使用了STL-set

注意当询问为0时,要输出"Yes"

[代码]

#include<bits/stdc++.h>
using namespace std;
#define MAXN 10010
#define MAXQ 110 struct Edge
{
int to,w,nxt;
} e[MAXN<<]; int i,n,q,tot,root,u,v,w,len;
int size[MAXN],head[MAXN],weight[MAXN],sum[MAXN],val[MAXN],a[MAXQ];
bool visited[MAXN],ans[MAXQ]; inline void addedge(int u,int v,int w)
{
tot++;
e[tot] = (Edge){v,w,head[u]};
head[u] = tot;
}
inline void getroot(int u,int fa,int total)
{
int i,v;
size[u] = ;
weight[u] = ;
for (i = head[u]; i; i = e[i].nxt)
{
v = e[i].to;
if (fa != v && !visited[v])
{
getroot(v,u,total);
size[u] += size[v];
weight[u] = max(weight[u],size[v]);
}
}
weight[u] = max(weight[u],total - size[u]);
if (weight[u] < weight[root]) root = u;
}
inline void dfs(int u,int fa)
{
int i,v,w;
val[++len] = sum[u];
for (i = head[u]; i; i = e[i].nxt)
{
v = e[i].to;
w = e[i].w;
if (v != fa && !visited[v])
{
sum[v] = sum[u] + w;
dfs(v,u);
}
}
}
inline void calc(int u)
{
int i,j,k,v,w;
set< int > s;
s.clear();
s.insert();
for (i = head[u]; i; i = e[i].nxt)
{
v = e[i].to;
w = e[i].w;
if (!visited[v])
{
sum[v] = w;
len = ;
dfs(v,u);
for (j = ; j <= len; j++)
{
for (k = ; k <= q; k++)
{
if (s.find(a[k] - val[j]) != s.end())
ans[k] = true;
}
}
for (j = ; j <= len; j++) s.insert(val[j]);
}
}
}
inline void work(int u)
{
int i,v;
visited[u] = true;
calc(u);
for (i = head[u]; i; i = e[i].nxt)
{
v = e[i].to;
if (!visited[v])
{
root = ;
getroot(v,,size[v]);
work(root);
}
}
} int main()
{ scanf("%d%d",&n,&q);
for (i = ; i < n; i++)
{
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
for (i = ; i <= q; i++) scanf("%d",&a[i]);
root = ;
size[] = weight[] = n;
getroot(,,n);
work(root);
for (i = ; i <= q; i++) printf((ans[i] || a[i] == ) ? "Yes\n" : "No\n"); return ;
}

最新文章

  1. Sublime Text 3 快捷键整理
  2. 工作中常用shell之ssh登陆不用输入&quot;yes&quot;
  3. [原]一个简单的Linux TCP Client所涉及到的头文件
  4. 转】mysql数据库delete数据时不支持表别名
  5. JAVA:二进制(原码 反码 补码),位运算,移位运算,约瑟夫问题(5)
  6. 【转】Android编译系统详解(三)——编译流程详解
  7. oracle 的 SDO_GEOMETRY
  8. 小白对Salesforce的简单认识(01)
  9. EffectiveTensorflow:Tensorflow 教程和最佳实践
  10. 【一天一道LeetCode】#81. Search in Rotated Sorted Array II
  11. sequelize问题集锦
  12. animation 动画
  13. 闲记 单元格与单元格之间的边 ///字体属性都是font开头,除了颜色属性 ///文本属性都是text开的,除了设置行高。
  14. JavaEE 之 Spring(一)
  15. bzoj3255 一个关于序列的游戏
  16. C# 控件
  17. monit
  18. c++——对象的构造和析构函数、构造函数的分类及调用
  19. Python: 二进制、八进制、十六进制转换或者输出
  20. [洛谷P2747] [USACO5.4]周游加拿大Canada Tour

热门文章

  1. C# 线程知识汇总
  2. Kafka学习笔记(2)----Kafka的架构
  3. vue.js怎样将时间戳转化为日期格式
  4. mysql_connect() 不支持 请检查 mysql 模块是否正确加载
  5. Python内置数据结构之元组tuple
  6. Ubuntu 16.04 安装python3.6 环境并设置为默认
  7. RemoveAll测试
  8. C# word生成html
  9. WSDL详解(一)
  10. nyoj25-A Famous Music Composer