洛谷P3806 【模板】点分治1
2018-06-17 21:25:58来源:未知 阅读 ()
题目背景
感谢hzwer的点分治互测。
题目描述
给定一棵有n个点的树
询问树上距离为k的点对是否存在。
输入输出格式
输入格式:
n,m 接下来n-1条边a,b,c描述a到b有一条长度为c的路径
接下来m行每行询问一个K
输出格式:
对于每个K每行输出一个答案,存在输出“AYE”,否则输出”NAY”(不包含引号)
输入输出样例
2 1 1 2 2 2
AYE
说明
对于30%的数据n<=100
对于60%的数据n<=1000,m<=50
对于100%的数据n<=10000,m<=100,c<=1000,K<=10000000
自己YY出来的一种做法
慢的跟暴力一样
我们考虑点分治的过程,
用点分治可以快速计算出一个点到其他点的距离
在这些距离中,不同子树的可以相加,同一子树的不能相加,需要特判
对于查询操作,直接用数组记录权值为$k$的点是否出现过
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; const int MAXN=1e6+10; const int INF=1e7+10; inline char nc() { static char buf[MAXN],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++; } inline int read() { char c=nc();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();} return x*f; } struct node { int u,v,w,nxt; }edge[MAXN]; int head[MAXN]; int num=1; inline void AddEdge(int x,int y,int z) { edge[num].u=x; edge[num].v=y; edge[num].w=z; edge[num].nxt=head[x]; head[x]=num++; } int F[MAXN],sum,siz[MAXN],vis[MAXN],root=0,cnt=0,deep[MAXN],can[MAXN]; struct Ans { int v,id; }tot[MAXN]; void GetRoot(int now,int fa) { siz[now]=1; for(int i=head[now];i!=-1;i=edge[i].nxt) { if(vis[edge[i].v]||edge[i].v==fa) continue; GetRoot(edge[i].v,now); siz[now]+=siz[edge[i].v]; F[now]=max(F[now],siz[edge[i].v]); } F[now]=max(F[now],sum-F[now]); if(F[now]<F[root]) root=now; } void GetDeep(int now,int fa,int NowDeep,int num) { int cur=0; tot[++cnt].v=deep[now]; tot[cnt].id=num; for(int i=head[now];i!=-1;i=edge[i].nxt) { if(vis[edge[i].v]||edge[i].v==fa) continue; deep[edge[i].v]=deep[now]+edge[i].w; if(NowDeep!=1) GetDeep(edge[i].v,now,NowDeep+1,num); else GetDeep(edge[i].v,now,NowDeep+1,cur++); } } void Work(int now) { cnt=0;deep[now]=0; GetDeep(now,0,1,1); for(int i=1;i<=cnt;i++) for(int j=i+1;j<=cnt;j++) if(tot[i].id!=tot[j].id) can[tot[i].v+tot[j].v]=1; else can[tot[i].v]=1,can[tot[j].v]=1; } void Solve(int now) { Work(now); vis[now]=1; for(int i=head[now];i!=-1;i=edge[i].nxt) { if(vis[edge[i].v]) continue; root=0; sum=siz[edge[i].v]; GetRoot(edge[i].v,0); Solve(edge[i].v); } } int main() { #ifdef WIN32 freopen("a.in","r",stdin); #else #endif memset(head,-1,sizeof(head)); int N=read(),M=read(); for(int i=1;i<=N-1;i++) { int x=read(),y=read(),z=read(); AddEdge(x,y,z); AddEdge(y,x,z); } root=0; F[0]=INF; sum=N; GetRoot(1,0); Solve(root); for(int i=1;i<=M;i++) { int p=read(); if(can[p]) printf("AYE\n"); else printf("NAY\n"); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:森炊的预算方案
下一篇:Qt 5中信号和槽的新语法
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- C++ 模板类vector 2020-05-31
- C++ 模板类array 2020-05-31
- C++ 模板类vector 2020-05-30
- 洛谷P1164->小A点菜 2020-05-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash