BZOJ 1316: 树上的询问 （点分治+set）
题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1316
因为只要求存在某条路径长度为K，所以点分，然后用set判断差值是否在set中就可以了。
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<queue>
#include<set>
#include<cmath>
#define rep(i,l,r) for (int i=l;i<=r;i++)
#define down(i,l,r) for (int i=l;i>=r;i--)
#define clr(x,y) memset(x,y,sizeof(x))
#define maxn 10900
#define inf int(1e9)
#define mm 1000000007
#define esp 1e-6
using namespace std;
#define ll long long
struct data{int obj,pre; ll c;
}e[maxn*2];
int head[maxn],s[maxn],ans[maxn],q[maxn],vis[maxn];
int n,m,tot,sum,mn,rt;
set<ll> bst;
int read(){
int x=0,f=1; char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}
void insert(int x,int y,int z){
e[++tot].obj=y; e[tot].pre=head[x]; e[tot].c=z; head[x]=tot;
}
void dfs(int u,int fa){
s[u]=1;
int mx=0;
for (int j=head[u];j;j=e[j].pre){
int v=e[j].obj;
if (!vis[v]&&v!=fa){
dfs(v,u);
s[u]+=s[v];
mx=max(mx,s[v]);
}
}
mx=max(sum-mx,mx);
if (mx<mn) mn=mx,rt=u;
}
void add(int u,int fa,ll w){
bst.insert(w);
for (int j=head[u];j;j=e[j].pre){
int v=e[j].obj;
if (v!=fa&&!vis[v])add(v,u,w+e[j].c);
}
}
void update(int u,int fa,ll w){
rep(i,1,m) if (!ans[i])
ans[i]|=(bst.find(q[i]-w)!=bst.end());
for (int j=head[u];j;j=e[j].pre){
int v=e[j].obj;
if (v!=fa&&!vis[v]) update(v,u,w+e[j].c);
}
}
void solve(int u){
mn=inf;
dfs(u,0);
u=rt;
bst.clear(); bst.insert(0);
for (int j=head[u];j;j=e[j].pre){
int v=e[j].obj;
if (!vis[v]) update(v,u,e[j].c),add(v,u,e[j].c); //先判断点再加边。
}
vis[u]=1;
for (int j=head[u];j;j=e[j].pre){
int v=e[j].obj;
if (!vis[v]){
sum=s[v];
solve(v);
}
}
}
int main(){
n=read(); m=read();
int x,y,z;
rep(i,1,n-1){
x=read(); y=read(); z=read();
insert(x,y,z);
insert(y,x,z);
}
rep(i,1,m) q[i]=read();
sum=n;
solve(1);
rep(i,1,m) if(!q[i]) ans[i]=1; //如果q[i]=0，那么可以只选取一个点。
rep(i,1,m) if (ans[i]) puts("Yes"); else puts("No");
return 0;
}
最新文章
- Android零散
- orcad 元件库的查找位置对照表
- oc 正则图片<img /> 标签
- 使用 EPUB 制作数字图书
- ReactJS入门二
- 【iOS】MD5数据加密和网络安全
- js在关闭页面前弹出确认提示【转载】
- css3 3d初入门（一）
- linux（十二）之用户管理
- 关于STM32驱动DS1302实时时钟的一点思考
- mysql索引使用注意事项
- 面向对象编程之super内置函数的用法
- vue 组件按需引用，vue-router懒加载，vue打包优化，加载动画
- javascript小记一则：今天在写VS2005——.NET程序时，写的一个JS图片示例案例
- Spring AOP 的实现机制
- 随机森林学习-sklearn
- 关于StringUtils的常用方法
- Servlet WebSocket的简易聊天室
- 解析Service之你需要了解的一些东东
- Django -- settings 详解（转）