例题#
题目描述#
给定一棵有
输入格式#
第一行两个数
第
接下来
输出格式#
对于每次询问输出一行一个字符串代表答案，存在输出 AYE，否则输出 NAY。
样例 #1#
样例输入 #1#
2 1
1 2 2
2样例输出 #1#
AYE数据规模与约定#
- 对于
的数据，保证 。 - 对于
的数据，保证 ， 。 - 对于
的数据，保证 ， ， ， ， 。
{% raw %}
{% endraw %}
{% endraw %}
基本思想#
点分治，顾名思义就是基于树上的节点进行分治。
如果我们在深入一点呢？对于点的拆开其实就是对于树的拆开。
所以我认为点分治的本质其实是将一棵树拆分成许多棵子树处理，并不断进行。
这应该也是点分治的精髓。
既然我们要将一个点进行分治，那么选点肯定最首要的。
思考下面一个问题：
如果树退化为一个链，
我们选取链首作为分治点，理论时间复杂度？
而如果选择链的中心，它的理论时间复杂度又是多少？
选择链首：
选择链心：
通过这个例子,我们不难发现：
如果选点后左右子树越大，递归层数越多，时间越慢，反之则越快。
所以我们的选点标准就出来了，而我们把有这个性质的点叫做：树的重心！
求解树的重心#
void getroot(int now,int fa){
tree[now].size=1,tree[now].mx=0; //初始化当前树
for(auto i : tree[now].to){ //遍历每棵子树
if(i.to==fa || tree[i.to].usd) continue; //特判，防止死循环
getroot(i.to,now); //递归查找根
tree[now].size+=tree[i.to].size; //重新计算子树大小
tree[now].mx=max(tree[now].mx,tree[i.to].size); //找出最大子树
}
tree[now].mx=max(tree[now].mx,tree[0].mx-tree[now].size);
/*此处 tree[0].mx-tree[now].size
因为父节点也有大小；因此要将父节点算入
*/
if(tree[now].mx<tree[root].mx) root=now; //优化选根
}分治中心算法#
void divid(int now){
calc(now);
tree[now].usd=true;
for(auto i : tree[now].to){
if(!tree[i.to].usd){
root=0;
tree[0].mx=tree[i.to].size;
getroot(i.to,0),getroot(root,0);
divid(root);
}
}
}{% raw %}
{% raw %}
{% endraw %}
{% endraw %}
#include<iostream>
#include <vector>
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
return x*f;
}
int n,m,d[26005],hav[10000005],cnt=0;
int ans[26005];
struct ro{
int to;
int val;
};
struct node{
vector <ro> to;
int size;
int dis;
int mx;
bool usd;
}tree[50005];
int root;
void getroot(int now,int fa){
tree[now].size=1,tree[now].mx=0;
for(auto i : tree[now].to){
if(i.to==fa || tree[i.to].usd) continue;
getroot(i.to,now);
tree[now].size+=tree[i.to].size;
tree[now].mx=max(tree[now].mx,tree[i.to].size);
}
tree[now].mx=max(tree[now].mx,tree[0].mx-tree[now].size);
if(tree[now].mx<tree[root].mx) root=now;
}
void getdis(int now,int fa){
d[++cnt]=tree[now].dis;
for(auto i : tree[now].to){
if(i.to==fa||tree[i.to].usd) continue;
tree[i.to].dis=tree[now].dis+i.val;
getdis(i.to,now);
}
}
void calc(int now){
hav[0]=1;
vector<int>v;
for(auto i : tree[now].to){
if(tree[i.to].usd)continue;
cnt=0;
tree[i.to].dis=i.val;
getdis(i.to,now);
for(int j = 1;j<=cnt;j++){
for(int k = 1;k<=m;k++){
if(k>=d[j]) ans[k] |=hav[k-d[j]];
}
}
for(int j = 1;j<=cnt;j++){
if(d[j]<=1e7){
hav[d[j]] =1;
v.push_back(d[j]);
}
}
}
for(auto i:v){
hav[i]=0;
}
}
void divid(int now){
calc(now);
tree[now].usd=true;
for(auto i : tree[now].to){
if(!tree[i.to].usd){
root=0;
tree[0].mx=tree[i.to].size;
getroot(i.to,0),getroot(root,0);
divid(root);
}
}
}
int main(){
n=read();
int u,v,w;
for(int i = 1;i<n;i++){
u=read(),v=read(),w=read();
tree[u].to.push_back((ro){v,w});
tree[v].to.push_back((ro){u,w});
}
m=read();
tree[0].mx=n;
getroot(1,0),getroot(root,0);
divid(root);
long long sum=0;
for(int i = 1;i<=m;i++) sum+=ans[i];
cout<<sum;
return 0;
}
{% raw %}
Comments
View on GitHub