[Luogu P3806] 【模板】点分治1

[Luogu P3806] 【模板】点分治1

思路

达成成就:20min内打+调简单的点分治(当然比起10min2k的cz小神童还是很菜啦)

很简单的点分治板子题qwq,每层分治用一个vector记录已有的路径长度,对于全局运用一个bool数组记录每种路径长度的存在性即可

代码

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

struct Edge;
struct Node{
	Edge *head;
	int siz, mx, dep;
	bool vis;
}node[10010], *root;
struct Edge{
	Node *to;
	Edge *ne;
	int val;
	Edge(int x, int y, int z) : to(&node[y]), ne(node[x].head), val(z){}
};
int N, SumSiz;
bool exi[10000010];
vector<int>qwq;

void getroot(Node *x, Node *fa){
	x->siz=1, x->mx=0;
	for(Edge *i=x->head; i; i=i->ne){
		if(i->to==fa || i->to->vis)	continue;
		getroot(i->to, x);
		x->siz+=i->to->siz;
		x->mx=max(x->mx, i->to->siz);
	}
	x->mx=max(x->mx, SumSiz-x->siz);
	root=root ? (x->mx<root->mx ? x : root) : x;
}

void dfs1(Node *x, Node *fa){
	for(int i=0; i<qwq.size(); i++)
		if(qwq[i]+x->dep<=10000000)
			exi[qwq[i]+x->dep]=true;
		else
			break;
	for(Edge *i=x->head; i; i=i->ne){
		if(i->to->vis || i->to==fa)	continue;
		i->to->dep=x->dep+i->val;
		dfs1(i->to, x);
	}
}

void dfs2(Node *x, Node *fa){
	qwq.push_back(x->dep);
	for(Edge *i=x->head; i; i=i->ne){
		if(i->to->vis || i->to==fa)	continue;
		dfs2(i->to, x);
	}
}

void divide(Node *x){
	x->vis=true;
	qwq.clear();
	qwq.push_back(0);
	for(Edge *i=x->head; i; i=i->ne){
		if(i->to->vis)	continue;
		i->to->dep=i->val;
		dfs1(i->to, NULL);
		dfs2(i->to, NULL);
	}
	for(Edge *i=x->head; i; i=i->ne){
		if(i->to->vis)	continue;
		SumSiz=i->to->siz, root=NULL;
		getroot(i->to, NULL);
		divide(root);
	}
}

int main(){
	int M, K, x, y, z;
	scanf("%d%d", &N, &M);
	for(int i=1; i<N; i++){
		scanf("%d%d%d", &x, &y, &z);
		node[x].head=new Edge(x, y, z);
		node[y].head=new Edge(y, x, z);
	} 
	SumSiz=N, root=NULL;
	getroot(&node[1], NULL);
	divide(root);
	while(M--){
		scanf("%d", &x);
		printf(exi[x] ? "AYE\n" : "NAY\n");
	}
	return 0;
} 

[Luogu P3806] 【模板】点分治1》有1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注