1316: 树上的询问

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1017  Solved: 287
[Submit][Status][Discuss]

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.

做完此题可看下POJ 3237 Tree

Source

 #include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define maxn 100000
using namespace std;
int n,q;
int ask[maxn];
int ans[maxn];
struct edge {
int to,next,c;
}e[maxn*];
int head[maxn],cnt;
void add(int u,int v,int c){e[cnt].to=v;e[cnt].next=head[u];e[cnt].c=c;head[u]=cnt++;}
int root;
int vis[maxn],size[maxn],sum,f[maxn];
void findrt(int x,int fa) {
size[x]=;f[x]=;
for(int i=head[x];i>=;i=e[i].next) {
int to=e[i].to;if(to==fa||vis[to]) continue;
findrt(to,x);
size[x]+=size[to];
f[x]=max(f[x],size[to]);
}
f[x]=max(f[x],sum-size[x]);
if(f[x]<f[root]) root=x;
}
int dis[maxn],t[maxn],tt,tmp,num[maxn];
int dfs(int x,int fa,int d) {
dis[++tt]=d;
for(int i=head[x];i>=;i=e[i].next) {
int to=e[i].to;if(to==fa||vis[to]) continue;
dfs(to,x,d+e[i].c);
}
}
void cal(int x,int fl,int d) {
tt=;tmp=;
dfs(x,,d);
sort(dis+,dis+tt+);
for(int i=;i<=tt;i++) {
if(dis[i]!=dis[i-]||i==) dis[++tmp]=dis[i],num[tmp]=;
else num[tmp]++;
}
for(int i=;i<=q;i++) {
for(int j=;j<=tmp;j++)
if(num[j]>=&&dis[j]*==ask[i]) ans[i]+=fl*num[j]*(num[j]-);
int l=,r=tmp;
while(l<r) {
if(dis[l]+dis[r]>ask[i]&&l<r) r--;
else {
if(dis[l]+dis[r]==ask[i]) ans[i]+=fl*num[l]*num[r];
l++;
}
}
} }
void work(int x) {
vis[x]=;cal(x,,);
for(int i=head[x];i>=;i=e[i].next) {
int to=e[i].to;if(vis[to]) continue;
cal(to,-,e[i].c);
root=;sum=size[to];findrt(to,x);
work(root);
}
}
int main() {
memset(head,-,sizeof(head));
scanf("%d%d",&n,&q);
for(int i=;i<n;i++) {
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);add(b,a,c);
}
for(int i=;i<=q;i++) scanf("%d",&ask[i]);
f[]=;sum=n;
findrt(,);
work(root);
for(int i=;i<=q;i++)
if(ans[i]>||!ask[i]) printf("Yes\n");
else printf("No\n");
}

最新文章

  1. CozyRSS开发记录4-抽屉效果订阅列表栏
  2. java 执行jar指定log4j.properties文件位置
  3. 敏捷开发方法-Scrum
  4. DP编辑距离
  5. VBS基础篇 - 常用函数
  6. nginx上如何支持.htaccess伪静态转向
  7. 【Qt】Qt之自定义界面(窗体缩放)【转】
  8. C#中,表达式的计算遵循一个规律:从左到右依次计算。
  9. M3U8格式解说及实际应用分析
  10. TCP协议详解
  11. Mysql 用法
  12. nginx error.log 提示 [error] 887#887: *58 FastCGI sent in stderr: &quot;PHP message: PHP Warning: mysql_connect(): Headers and client library minor version mismatch. Headers:50556 Library:50637
  13. FFT与一些冷门问题
  14. LeetCode OJ 129. Sum Root to Leaf Numbers
  15. Linux基础笔记—— 走进Linux
  16. hello1分析
  17. 如何安装Exchange2010上安装更新汇总(Update Rollup)
  18. .NET:枚举的默认值
  19. FileTable使用总结
  20. IOC疑惑

热门文章

  1. poi解析excel出现格式不正确
  2. Hibernate查询语言——HQL
  3. [洛谷P4015]运输问题
  4. Windows查看进程CMD命令和终止进程CMD命令
  5. 安徽师大附中%你赛day7 T2 乘积 解题报告
  6. angular js的Inline Array Annotation的理解
  7. shell监控进程是否存在
  8. Spring学习--基于 XML 的配置声明切面
  9. C# 序列化理解 2(转)
  10. 3中转换JSON数据的方式