P3806 【模板】点分治1(CDQ分治)

题目链接:https://www.luogu.org/problemnew/show/P3806

题目大意:中文题目

具体思路:直接dfs好像会超时,然后我们就开始想优化的方法,然后就是一个CDQ入门题了,我们可以分解成许多子问题进行解决,然后对于一棵树的话,我们最好的切入点就是这棵树的重心了,这样就能使得复杂度尽可能的低了,然后就不停的往下递归找每一棵子树的重心进行求解就可以了,然后注意去重。

AC代码:

 #include<bits/stdc++.h>
using namespace std;
# define ll long long
# define inf 0x3f3f3f3f
const int maxn = 1e6+;
# define inf 0x3f3f3f3f
struct node
{
int to;
int nex;
int cost;
} edge[maxn<<];
int head[maxn<<],num=;
int dis[maxn],ans[maxn],mx[maxn];
int S,root;
int Size[maxn],vis[maxn];
int n,m,tot=;
void addedge(int fr,int to,int cost)
{
edge[num].to=to;
edge[num].cost=cost;
edge[num].nex=head[fr];
head[fr]=num++;
}
void Find(int x,int rt)
{
Size[x]=;
mx[x]=;
for(int i=head[x]; i!=-; i=edge[i].nex)
{
int to=edge[i].to;
if(to==rt||vis[to])
continue;
Find(to,x);
Size[x]+=Size[to];
mx[x]=max(mx[x],Size[to]);
}
mx[x]=max(mx[x],S-Size[x]);
if(mx[x]<mx[root])
root=x;
}
int a[maxn];
void get_dis(int x,int len,int rt)
{
dis[++tot]=a[x];
for(int i=head[x]; i!=-; i=edge[i].nex)
{
int to=edge[i].to;
if(to==rt||vis[to])
continue;
a[to]=len+edge[i].cost;
get_dis(to,len+edge[i].cost,x);
}
}
void solve(int x,int len,int w)
{
tot=;
a[x]=len;
get_dis(x,len,);
for(int i=; i<=tot; i++)
{
for(int j=; j<=tot; j++)
{
if(i==j)
continue;
ans[dis[i]+dis[j]]+=w;
}
}
}
void divide(int x)
{
solve(x,,);
vis[x]=;
for(int i=head[x]; i!=-; i=edge[i].nex)
{
int to=edge[i].to;
if(vis[to])
continue;
solve(to,edge[i].cost,-);//去重
S=Size[x],root=,mx[]=Size[x];
Find(to,x);
divide(root);
}
}
int main()
{
memset(head,-,sizeof(head));
scanf("%d %d",&n,&m);
int st,ed,cost;
for(int i=; i<n; i++)
{
scanf("%d %d %d",&st,&ed,&cost);
addedge(st,ed,cost);
addedge(ed,st,cost);
}
S=n,root=,mx[]=n;
Find(,);
divide(root);
int tmp;
for(int i=; i<=m; i++)
{
scanf("%d",&tmp);
printf("%s\n",ans[tmp]?"AYE":"NAY");
}
return ;
}
上一篇:WPF四年,尤不足以替代WinForm


下一篇:UOJ#62. 【UR #5】怎样跑得更快 数论 莫比乌斯反演