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