首页 > 代码库 > 【Tsinsen-A1486】树（王康宁） 点分治 + Trie

【Tsinsen-A1486】树（王康宁） 点分治 + Trie

2024-09-01 19:08:41   220人阅读

A1486. 树（王康宁）

时间限制：1.0s   内存限制：512.0MB  
总提交次数：455   AC次数：97   平均分：52.62
查看未格式化的试题   提交   试题讨论
试题来源
　　2013中国国家集训队第二次作业
问题描述
　　给出一棵N个点的树，每个点有各自的权值，小A想选出一条简单路径，使得这条路径上的点的权值的异或和最大。另外，小A有一些喜欢的点，他希望在这条路径上经过至少K个自己喜欢的点。
输入格式
　　第一行包括两个整数N, K，分别表示树的点数和路径上至少包含的小A喜欢的点的数量。
　　接下来一行N个整数，每个数均为0或1，小A喜欢第i个点当且仅当这一行的第i个数是1。
　　接下来一行N个整数V1, V2, …, VN，其中第i个数表示第i个点的权值。
　　最后N-1行，每行两个整数u, v，表示树的一条边。
输出格式
　　如果不存在这样的简单路径，输出-1。否则输出最大的异或和。
样例输入
3 1
1 1 1
0 4 7
1 2
2 3
样例输出
7
样例输入
3 2
1 0 1
3 5 6
1 2
2 3
样例输出
0
样例输入
4 4
1 1 1 1
10 10 10 10
1 2
1 3
1 4
样例输出
-1
数据规模和约定
测试点标号
N的范围
K的范围
Vi的范围
其它特点
1
N=2
K=0


2
N≤10



3
N≤1000


这棵树是一条链
4
N≤1000
K=0

这棵树是一条链
5
N≤4000



6
N≤30000
K=0
Vi≤7

7
N≤40000
K=0


8
N≤40000
K=0


9
N≤50000
K=0

这棵树是一条链
10
N≤50000
K=0


11
N≤60000

Vi≤7

12
N≤60000


这棵树是一条链
13
N≤70000

Vi≤107

14
N≤70000

Vi≤107

15
N≤80000



16
N≤80000



17
N≤90000



18
N≤90000



19
N≤100000



20
N≤100000



　　对于100%的数据，1≤N≤100000, 0≤K≤N, 0≤Vi≤109, 保证输入的是一棵合法的树.

Solution

这道题，先考虑弱化版本..

如果$K=0$不考虑经过关键点的数量，非常简单。

可以直接从根dfs一遍得到到所有节点的xor和，然后全部插入Trie中，再枚举每个点贪心在Trie上跑即可，复杂度$O(NlogN)$。

但是这个题需要限制经过节点数，就必须点分治+Trie贪心，时间复杂度$O(Nlog^{2}N)$。

最普通的想法就是对于经过不同的关键点的路径xor和分别建一棵Trie树，然后查询的时候查询即可，但是$K$上限过大。

所以考虑维护一棵Trie树，在每个节点上维护一下经过的关键点数，在贪心统计答案的时候处理一下即可。

这里有一个问题，就是处理一棵子树的时候，最顶部的节点会重复计算，所以可以考虑先不计算它的影响，在统计答案的时候再计算回来。

Code

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>using namespace std;inline int read(){	int x=0,f=1; char ch=getchar();	while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();}	while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();}	return x*f;}#define MAXN 100010int N,K,lov[MAXN],c[MAXN],ans=-1;struct EdgeNode{	int next,to;}edge[MAXN<<1];int head[MAXN],cnt=1;inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}inline void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}namespace Trie{	int son[MAXN][2],sz,d[MAXN];	int s[32];	inline void Calc(int x) {memset(s,0,sizeof(s)); for (int t=31; t>=0; t--) s[t]=(x>>t)&1;}	inline void Clear() {son[1][0]=son[1][1]=0; sz=1;}	inline void Insert(int x,int dep) 	{		int now=1;		Calc(x);		for (int i=31; i>=0; i--)			if (son[now][s[i]]) now=son[now][s[i]],d[now]=max(d[now],dep);				else son[now][s[i]]=++sz,now=sz,son[now][1]=son[now][0]=0,d[now]=dep;	}	inline int Query(int x,int dep)	{		int now=1,mx=0;		Calc(x);		for (int i=31; i>=0; i--) {			if (son[now][s[i]^1] && d[son[now][s[i]^1]]>=dep) now=son[now][s[i]^1],mx|=(1<<i);				else if (son[now][s[i]] && d[son[now][s[i]]]>=dep) now=son[now][s[i]];					else return -1;		}		return mx;	}}using namespace Trie;namespace TreeDivide{	int size[MAXN],mx[MAXN],Sz,root;	bool visit[MAXN];	struct Node{		int x,y;		Node (int X=0,int Y=0) {x=X,y=Y;}	}stack[MAXN];	int top;	inline void Getroot(int now,int last)	{		size[now]=1,mx[now]=0;		for (int i=head[now]; i; i=edge[i].next)			if (edge[i].to!=last && !visit[edge[i].to]) {				Getroot(edge[i].to,now);				size[now]+=size[edge[i].to];				mx[now]=max(mx[now],size[edge[i].to]);			}		mx[now]=max(mx[now],Sz-size[now]);		if (mx[now]<mx[root]) root=now;	}	inline void DFS(int now,int last,int dep,int val,int fav)	{		ans=max(ans,Query(val^fav,K-dep));		stack[++top]=Node(val,dep);		for (int i=head[now]; i; i=edge[i].next)			if (edge[i].to!=last && !visit[edge[i].to]) {				DFS(edge[i].to,now,dep+lov[edge[i].to],val^c[edge[i].to],fav);			}	}	inline void Divide(int now)	{//		printf("root=%d\n",now);		visit[now]=1;		Trie::Clear();		K-=lov[now];		if (K<=0) ans=max(ans,c[now]);		for (int i=head[now]; i; i=edge[i].next)			if (!visit[edge[i].to]) {				top=0;				DFS(edge[i].to,now,lov[edge[i].to],c[edge[i].to],c[now]);				for (int j=1; j<=top; j++)					Trie::Insert(stack[j].x,stack[j].y);			}		K+=lov[now];		for (int i=head[now]; i; i=edge[i].next) 			if (!visit[edge[i].to]) {				root=0;				Sz=size[edge[i].to];				Getroot(edge[i].to,now);				Divide(root);			}	}}using namespace TreeDivide;int main(){	N=read(),K=read();	for (int i=1; i<=N; i++) lov[i]=read();	for (int i=1; i<=N; i++) c[i]=read();	for (int i=1,x,y; i<=N-1; i++) x=read(),y=read(),InsertEdge(x,y);	mx[root=0]=Sz=N;	Getroot(1,0);	Divide(root);	printf("%d\n",ans);	return 0;}

 

【Tsinsen-A1486】树（王康宁） 点分治 + Trie


联系
我们