【BZOJ1316】树上的询问

Description

一棵n个点的带权有根树,有p个询问,每次询问树中是否存在一条长度为Len的路径,如果是,输出Yes否输出No.

Input

第一行两个整数n, p分别表示点的个数和询问的个数. 接下来n-1行每行三个数x, y, c,表示有一条树边x→y,长度为c. 接下来p行每行一个数Len,表示询问树中是否存在一条长度为Len的路径.

Output

输出有p行,Yes或No.

Sample Input

6 4
1 2 5
1 3 7
1 4 1
3 5 2
3 6 3
1
8
13
14

Sample Output

Yes
Yes
No
Yes

HINT

30%的数据,n≤100. 
100%的数据,n≤10000,p≤100,长度≤1000000.

题解:直接点分治。本题可以采用树形DP形态的点分治,用set维护在x的第1..i-1号儿子的所有子树中,所有出现过的深度,然后在扫第i个儿子时顺便用(Len-当前dep)在set里找一下更新答案。复杂度O(nlog2n*100)。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
const int maxn=10010;
int n,m,cnt,tot,rt,mn;
int to[maxn<<1],next[maxn<<1],val[maxn<<1],siz[maxn],head[maxn],q[110],ans[110],vis[maxn],p[maxn];
set<int> s;
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
void add(int a,int b,int c)
{
to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;
}
void getrt(int x,int fa)
{
siz[x]=1;
int i,tmp=0;
for(i=head[x];i!=-1;i=next[i]) if(to[i]!=fa&&!vis[to[i]])
getrt(to[i],x),siz[x]+=siz[to[i]],tmp=max(tmp,siz[to[i]]);
tmp=max(tmp,tot-siz[x]);
if(tmp<mn) mn=tmp,rt=x;
}
void getdep(int x,int fa,int dep)
{
int i;
p[++p[0]]=dep,siz[x]=1;
for(i=1;i<=m;i++) ans[i]|=(s.find(q[i]-dep)!=s.end());
for(i=head[x];i!=-1;i=next[i]) if(to[i]!=fa&&!vis[to[i]]) getdep(to[i],x,dep+val[i]),siz[x]+=siz[to[i]];
}
void dfs(int x)
{
vis[x]=1;
int i,j;
s.clear(),s.insert(0);
for(i=head[x];i!=-1;i=next[i]) if(!vis[to[i]])
{
p[0]=0,getdep(to[i],x,val[i]);
for(j=1;j<=p[0];j++) s.insert(p[j]);
}
for(i=head[x];i!=-1;i=next[i]) if(!vis[to[i]]) tot=siz[to[i]],mn=1<<30,getrt(to[i],x),dfs(rt);
}
int main()
{
n=rd(),m=rd();
int i,a,b,c;
memset(head,-1,sizeof(head));
for(i=1;i<n;i++) a=rd(),b=rd(),c=rd(),add(a,b,c),add(b,a,c);
for(i=1;i<=m;i++) q[i]=rd();
tot=n,mn=1<<30,getrt(1,0),dfs(rt);
for(i=1;i<=m;i++)
{
if(!q[i]||ans[i]) printf("Yes\n");
else printf("No\n");
}
return 0;
}

最新文章

  1. Mongoose全面理解
  2. 学习记录 java session保存用户登录
  3. 偶然发现关于网页JavaScript脚本无法正常运行的原因
  4. thymeleaf的初次使用(带参请求以及调用带参js方法)
  5. android99 拍照摄像
  6. POJ 1637 Sightseeing tour(最大流)
  7. webpack+React.js
  8. dbf导入sqlserver的方法
  9. ASP.NET Core 系列视频完结,新项目实战课程发布。
  10. Django【部署】uwsgi+nginx
  11. Python一些代码
  12. SpringCloud笔记四:Ribbon
  13. 从外部设置传入Go变量
  14. linux安装svn客户端rabbitvcs
  15. Nginx配置服务器静态文件支持跨域访问
  16. L与_T
  17. springMVC自定义方法属性解析器
  18. PriorityQueue的Java实现
  19. Vue 项目添加 promise polyfill
  20. 实现观察者模式(Observer Pattern)的2种方式

热门文章

  1. 【原创】Word2010 清除样式
  2. 联通积分兑换的Q币怎么兑换到QQ上
  3. Codeforces 509E Pretty Song (思维)
  4. centos7下使用wget命令安装mysql
  5. BZOJ 4543 2016北京集训测试赛(二)Problem B: thr
  6. Google开源基于Tensorflow的NLP框架重大升级
  7. Linux ClientDataSet libmidas.so.2
  8. cocos2dx 2.x新建项目
  9. MySQL---SQL记录
  10. 2016.6.20 maven更改repository的位置