刚学OI，不会点分治
查看原帖
刚学OI，不会点分治
28088
钱逸凡楼主2020/11/22 19:28
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
inline int Read(){
	int x=0;
	char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	return x;
} 
const int mx=10100;
int n,m;
struct Edge{
	int v;
	int val;
	int next;
}edge[mx<<1];
int top,head[mx];
void addedge(int u,int v,int val){
	edge[++top].v=v;
	edge[top].next=head[u];
	edge[top].val=val;
	head[u]=top;
}
void add(int u,int v,int val){
	addedge(u,v,val);
	addedge(v,u,val);
}
int size[mx],maxn[mx];//每个点的子节点数量,每个点最大的子树大小 
int s;//当前树的点的总数 
int vis[mx];//该点是否被访问过 
int dist[mx];//每个点到重心的距离 
int root;//重心（分治中心） 
struct Path{
	int lenth;//路径长度
	int from;//从重心的哪个子节点出发的 
}path[mx];
bool cmp(Path a,Path b){
	return a.lenth<b.lenth;//按照路径长度排序 
}
int q[mx];//所有的询问 
int ans[mx];//询问是否成立 
int cnt;//当前路径数量 
void find(int u,int fa){//寻找当前树的重心 
	maxn[u]=0,size[u]=1;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].v;
		if(v==fa||vis[v])continue;//防止回到已经找过的区域 
		find(v,u);
		size[u]+=size[v];
		maxn[u]=max(maxn[u],size[v]);
	}
	maxn[u]=max(maxn[u],s-size[u]);//可能往上是最大的子树 
	if(maxn[u]<maxn[root])root=u;//更新重心 
}
void get_dist(int u,int fa,int start){
	path[++cnt]=(Path){dist[u],start};
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].v;
		if(v==fa||vis[v])continue;
		dist[v]=dist[u]+edge[i].val;
		get_dist(v,u,start);
	}
}
void cal(int u){
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].v;
		if(vis[v])continue;
		dist[v]=edge[i].val;
		get_dist(v,u,v);
	}
	sort(path+1,path+1+cnt,cmp);
	for(int i=1;i<=m;++i){//遍历所有询问 
		if(ans[i])continue;//其他子树中已经有该长度的路径了 
		for(int j=1;j<=cnt;++j){//先看看单条路径是否符合要求
			if(path[j].lenth==q[i]){
				ans[i]=1;
				break;
			}
		}
		if(ans[i])continue;//已经符合要求了就不用看两条路径相加了 
		int l=1,r=cnt;
		while(l<r){
			if(path[l].lenth+path[r].lenth<q[i])++l;//小了就左端点右移 
			else if(path[l].lenth+path[r].lenth>q[i])--r;//大了就右端点左移 
			else{
				if(path[l].from==path[r].from){//同一个子节点出发的路径不能相加
					if(path[r].lenth==path[r-1].lenth)--r;
					else if(path[l].lenth==path[l+1].lenth)++l;
					else break; 
				}
				else{//找到了符合要求的路径 
					ans[i]=1;
					break;
				}
			}
		}
	}
	
}
void solve(int u){
	vis[u]=1;//标记已经找过 
	cnt=0;//清空no 
	cal(u);//以当前节点为重心计算一次 
	int ss=s;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].v;
		if(vis[v])continue;
		s=size[v];
		if(size[v]>size[u])s=ss-size[u];
		root=0;
		maxn[0]=1<<30;//不能使0为重心 
		find(v,0);//找到子树的重心
		solve(root);//按照子树的重心重复操作 
	}
}
int main(){
//	freopen("in.txt","r",stdin);
	n=Read(),m=Read();
	for(int i=1;i<n;++i){
		int u=Read(),v=Read(),val=Read();
		add(u,v,val);
	}
	for(int i=1;i<=m;++i)q[i]=Read();
	maxn[0]=1<<30;//防止把0当成重心 
	find(1,0);//找初始重心 
	solve(root);
	for(int i=1;i<=m;++i)printf("%s\n",(ans[i]?"AYE":"NAY"));
	return 0;
}

这是一个T了的代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
inline int Read(){
	int x=0;
	char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	return x;
} 
const int mx=10100;
int n,m;
struct Edge{
	int v;
	int val;
	int next;
}edge[mx<<1];
int top,head[mx];
void addedge(int u,int v,int val){
	edge[++top].v=v;
	edge[top].next=head[u];
	edge[top].val=val;
	head[u]=top;
}
void add(int u,int v,int val){
	addedge(u,v,val);
	addedge(v,u,val);
}
int size[mx],maxn[mx];//每个点的子节点数量,每个点最大的子树大小 
int s;//当前树的点的总数 
int vis[mx];//该点是否被访问过 
int dist[mx];//每个点到重心的距离 
int root;//重心（分治中心） 
struct Path{
	int lenth;//路径长度
	int from;//从重心的哪个子节点出发的 
}path[mx];
bool cmp(Path a,Path b){
	return a.lenth<b.lenth;//按照路径长度排序 
}
int q[mx];//所有的询问 
int ans[mx];//询问是否成立 
int cnt;//当前路径数量 
void find(int u,int fa){//寻找当前树的重心 
	maxn[u]=0,size[u]=1;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].v;
		if(v==fa||vis[v])continue;//防止回到已经找过的区域 
		find(v,u);
		size[u]+=size[v];
		maxn[u]=max(maxn[u],size[v]);
	}
	maxn[u]=max(maxn[u],s-size[u]);//可能往上是最大的子树 
	if(maxn[u]<maxn[root])root=u;//更新重心 
}
void get_dist(int u,int fa,int start){
	path[++cnt]=(Path){dist[u],start};
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].v;
		if(v==fa||vis[v])continue;
		dist[v]=dist[u]+edge[i].val;
		get_dist(v,u,start);
	}
}
void cal(int u){
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].v;
		if(vis[v])continue;
		dist[v]=edge[i].val;
		get_dist(v,u,v);
	}
	sort(path+1,path+1+cnt,cmp);
	for(int i=1;i<=m;++i){//遍历所有询问 
		if(ans[i])continue;//其他子树中已经有该长度的路径了 
		for(int j=1;j<=cnt;++j){//先看看单条路径是否符合要求
			if(path[j].lenth==q[i]){
				ans[i]=1;
				break;
			}
		}
		if(ans[i])continue;//已经符合要求了就不用看两条路径相加了 
		int l=1,r=cnt;
		while(l<r){
			if(path[l].lenth+path[r].lenth<q[i])++l;//小了就左端点右移 
			else if(path[l].lenth+path[r].lenth>q[i])--r;//大了就右端点左移 
			else{
				if(path[l].from==path[r].from){//同一个子节点出发的路径不能相加
					if(path[r].lenth==path[r-1].lenth)--r;
					else if(path[l].lenth==path[l+1].lenth)++l;
					else break; 
				}
				else{//找到了符合要求的路径 
					ans[i]=1;
					break;
				}
			}
		}
	}
	
}
void solve(int u){
	vis[u]=1;//标记已经找过 
	cnt=0;//清空no 
	cal(u);//以当前节点为重心计算一次 
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].v;
		if(vis[v])continue;
		s=size[v];
		root=0;
		maxn[0]=1<<30;//不能使0为重心 
		find(v,0);//找到子树的重心
		solve(root);//按照子树的重心重复操作 
	}
}
int main(){
//	freopen("in.txt","r",stdin);
	n=Read(),m=Read();
	for(int i=1;i<n;++i){
		int u=Read(),v=Read(),val=Read();
		add(u,v,val);
	}
	for(int i=1;i<=m;++i)q[i]=Read();
	maxn[0]=1<<30;//防止把0当成重心 
	find(1,0);//找初始重心 
	solve(root);
	for(int i=1;i<=m;++i)printf("%s\n",(ans[i]?"AYE":"NAY"));
	return 0;
}

这是一个A了的代码

两份代码唯一的差别就是solve函数中s的值不同， 在T了的代码中，我的solve是这么写的：

void solve(int u){
	vis[u]=1;//标记已经找过 
	cnt=0;//清空no 
	cal(u);//以当前节点为重心计算一次 
	int ss=s;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].v;
		if(vis[v])continue;
		s=size[v];
		if(size[v]>size[u])s=ss-size[u];
		root=0;
		maxn[0]=1<<30;//不能使0为重心 
		find(v,0);//找到子树的重心
		solve(root);//按照子树的重心重复操作 
	}
}

而A了的代码中是这么写的：

void solve(int u){
	vis[u]=1;//标记已经找过 
	cnt=0;//清空no 
	cal(u);//以当前节点为重心计算一次 
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].v;
		if(vis[v])continue;
		s=size[v];
		root=0;
		maxn[0]=1<<30;//不能使0为重心 
		find(v,0);//找到子树的重心
		solve(root);//按照子树的重心重复操作 
	}
}

按照我的理解，A了的代码中找子树大小（即s)的写法应该是错的，因为如果v是u的父亲节点，s的值会出错，但是为什么这么写反而A了，另一种写法却会T呢？ 我看题解里很多都是按照A了的那种写法写的，但是不明白为什么，有没有好心的奆佬来帮帮忙啊

2020/11/22 19:28