模板题 P3806 【模板】点分治1
题目描述
给定一棵有 n 个点的树，询问树上距离为 k 的点对是否存在。
详讲
关于点分治具体内容可以看这个 这里主要是详细讲讲代码： getrt是用来求重心，我们利用树型dp的思维来做，即找到该节点所有的子树，找到最大的哪一颗即可
void getrt(int u
,int pa
)
{
size
[u
]=1; maxp
[u
]=0;
for(int i
=head
[u
];i
;i
=E
[i
].nxt
)
{
int v
=E
[i
].v
;
if(v
==pa
||vis
[v
]) continue;
getrt(v
,u
);
size
[u
]+=size
[v
];
maxp
[u
]=max(maxp
[u
],size
[v
]);
}
maxp
[u
]=max(maxp
[u
],sum
-size
[u
]);
if(maxp
[u
]<maxp
[rt
]) rt
=u
;
}
getdis是用来求每一个子节点到根的距离 getdis在calc中不断被调用
void getdis(int u
,int fa
)
{
rem
[++rem
[0]]=dis
[u
];
for(int i
=head
[u
];i
;i
=E
[i
].nxt
)
{
int v
=E
[i
].v
;
if(v
==fa
||vis
[v
])continue;
dis
[v
]=dis
[u
]+E
[i
].dis
;
getdis(v
,u
);
}
}
calc是用来合并答案的，因为在getdis中已经计算出所有点到根的距离，所以把任意两个出现的距离凑在一起，并】、判断可否凑出我们需要的k即可 rem[i]存的是在getdis中求出的距离，rem[0]这个值是值rem存了多少值 judge我们可以用来存距离，对已经出现的距离用judge标记为1，这样当出现另一个距离可以和这个距离搭配成我们所需的k时，就可以直接标记答案 judge[query[k]-rem[j]]; query[k]-rem[j]即为所需要的距离
test[k]|=judge[query[k]-rem[j]]; 用|就可以实现如果有就给test标记
void calc(int u
)
{
int p
=0;
for(int i
=head
[u
];i
;i
=E
[i
].nxt
)
{
int v
=E
[i
].v
;
if(vis
[v
])continue;
rem
[0]=0;
dis
[v
]=E
[i
].dis
;
getdis(v
,u
);
for(int j
=rem
[0];j
;--j
)
for(int k
=1;k
<=m
;++k
)
{
if(query
[k
]>=rem
[j
])
test
[k
]|=judge
[query
[k
]-rem
[j
]];
}
for(int j
=rem
[0];j
;--j
)
{
q
[++p
]=rem
[j
];
judge
[rem
[j
]]=1;
}
}
for(int i
=1;i
<=p
;++i
)
judge
[q
[i
]]=0;
}
solve则是对每一个根进行处理，通过solve来调用上述函数，在递归过程中不断重复一样的过程
void solve(int u
)
{
vis
[u
]=judge
[0]=1;
calc(u
);
for(int i
=head
[u
];i
;i
=E
[i
].nxt
)
{
int v
=E
[i
].v
;
if(vis
[v
])continue;
sum
=size
[v
];
maxp
[rt
=0]=inf
;
getrt(v
,0);
solve(rt
);
}
}
代码：
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std
;
int read()
{
int f
=1,x
=0;
char ss
=getchar();
while(ss
<'0'||ss
>'9'){if(ss
=='-')f
=-1;ss
=getchar();}
while(ss
>='0'&&ss
<='9'){x
=x
*10+ss
-'0';ss
=getchar();}
return f
*x
;
}
const int inf
=10000000;
const int maxn
=100010;
int n
,m
;
struct node
{int v
,dis
,nxt
;}E
[maxn
<<1];
int tot
,head
[maxn
];
int maxp
[maxn
],size
[maxn
],dis
[maxn
],rem
[maxn
];
int vis
[maxn
],test
[inf
],judge
[inf
],q
[maxn
];
int query
[1010];
int sum
,rt
;
int ans
;
void add(int u
,int v
,int dis
)
{
E
[++tot
].nxt
=head
[u
];
E
[tot
].v
=v
;
E
[tot
].dis
=dis
;
head
[u
]=tot
;
}
void getrt(int u
,int pa
)
{
size
[u
]=1; maxp
[u
]=0;
for(int i
=head
[u
];i
;i
=E
[i
].nxt
)
{
int v
=E
[i
].v
;
if(v
==pa
||vis
[v
]) continue;
getrt(v
,u
);
size
[u
]+=size
[v
];
maxp
[u
]=max(maxp
[u
],size
[v
]);
}
maxp
[u
]=max(maxp
[u
],sum
-size
[u
]);
if(maxp
[u
]<maxp
[rt
]) rt
=u
;
}
void getdis(int u
,int fa
)
{
rem
[++rem
[0]]=dis
[u
];
for(int i
=head
[u
];i
;i
=E
[i
].nxt
)
{
int v
=E
[i
].v
;
if(v
==fa
||vis
[v
])continue;
dis
[v
]=dis
[u
]+E
[i
].dis
;
getdis(v
,u
);
}
}
void calc(int u
)
{
int p
=0;
for(int i
=head
[u
];i
;i
=E
[i
].nxt
)
{
int v
=E
[i
].v
;
if(vis
[v
])continue;
rem
[0]=0; dis
[v
]=E
[i
].dis
;
getdis(v
,u
);
for(int j
=rem
[0];j
;--j
)
for(int k
=1;k
<=m
;++k
)
{
if(query
[k
]>=rem
[j
])
test
[k
]|=judge
[query
[k
]-rem
[j
]];
}
for(int j
=rem
[0];j
;--j
)
{
q
[++p
]=rem
[j
];
judge
[rem
[j
]]=1;
}
}
for(int i
=1;i
<=p
;++i
)
judge
[q
[i
]]=0;
}
void solve(int u
)
{
vis
[u
]=judge
[0]=1; calc(u
);
for(int i
=head
[u
];i
;i
=E
[i
].nxt
)
{
int v
=E
[i
].v
;
if(vis
[v
])continue;
sum
=size
[v
]; maxp
[rt
=0]=inf
;
getrt(v
,0); solve(rt
);
}
}
int main()
{
n
=read();m
=read();
for(int i
=1;i
<n
;++i
)
{
int u
=read(),v
=read(),dis
=read();
add(u
,v
,dis
);add(v
,u
,dis
);
}
for(int i
=1;i
<=m
;++i
)
query
[i
]=read();
maxp
[rt
]=sum
=n
;
getrt(1,0);
solve(rt
);
for(int i
=1;i
<=m
;++i
)
{
if(test
[i
]) printf("AYE\n");
else printf("NAY\n");
}
return 0;
}
