一、点分治。
题目①
Tree POJ - 1741：
Give a tree with n vertices,each edge has a length(positive integer less than 1001).
Define dist(u,v)=The min distance between node u and v.
Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.
Write a program that will count how many pairs which are valid for a given tree.
Input
The input contains several test cases. The first line of each test case contains two integers n, k. (n<=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l.
The last test case is followed by two zeros.
Output
For each test case output the answer on a single line.
Sample Input
5 4
1 2 3
1 3 1
1 4 2
3 5 1
0 0
Sample Output
8
树上两点之间距离小于等于k的点对的个数。
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=21000;
const int inf=0x3f3f3f3f;
int head[maxn],ver[maxn],edge[maxn],nt[maxn];
int max_part[maxn],_size[maxn];
bool ha[maxn];
int tot=1,root,max_size,ans=0,n,k;
vector<int>dis;
void init(void)
{
memset(head,0,sizeof(head));
memset(ha,0,sizeof(ha));
tot=1,ans=0;
}
void add(int x,int y,int z)
{
ver[++tot]=y,edge[tot]=z;
nt[tot]=head[x],head[x]=tot;
}
void dfs_size(int x,int fa)
{
_size[x]=1,max_part[x]=0;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(ha[y]||y==fa) continue;
dfs_size(y,x);
_size[x]+=_size[y];
max_part[x]=max(max_part[x],_size[y]);
}
}
void dfs_root(int now_root,int x,int fa)
{
max_part[x]=max(max_part[x],_size[now_root]-_size[x]);
if(max_size>max_part[x])
{
max_size=max_part[x];
root=x;
}
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(ha[y]||y==fa) continue;
dfs_root(now_root,y,x);
}
}
void dfs_dis(int x,int fa,int diss)
{
dis.push_back(diss);
for(int i=head[x];i;i=nt[i])
{
int y=ver[i],z=edge[i];
if(ha[y]||y==fa) continue;
dfs_dis(y,x,diss+z);
}
}
int get_num(int x,int d)
{
dis.clear();
dfs_dis(x,-1,d);
sort(dis.begin(),dis.end());
int i=0,j=dis.size()-1,res=0;
while(i<j)
{
while(dis[i]+dis[j]>k&&i<j) j--;
res+=j-i;
i++;
}
return res;
}
void dfs(int x)
{
max_size=inf;
dfs_size(x,-1);
dfs_root(x,x,-1);
ans+=get_num(root,0);
ha[root]=1;
for(int i=head[root];i;i=nt[i])
{
int y=ver[i],z=edge[i];
if(ha[y]) continue;
ans-=get_num(y,z);
dfs(y);
}
}
int main(void)
{
while(scanf("%d%d",&n,&k),n||k)
{
init();
int x,y,z;
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);add(y,x,z);
}
dfs(1);
printf("%d\n",ans);
}
return 0;
}
题目②
P3806 【模板】点分治1：
题目背景
感谢hzwer的点分治互测。
题目描述
给定一棵有n个点的树
询问树上距离为k的点对是否存在。
输入格式
n,m 接下来n-1条边a,b,c描述a到b有一条长度为c的路径
接下来m行每行询问一个K
输出格式
对于每个K每行输出一个答案，存在输出“AYE”,否则输出”NAY”(不包含引号)
输入输出样例
输入 #1 复制
2 1
1 2 2
2
输出 #1 复制
AYE
说明/提示
对于30%的数据n<=100
对于60%的数据n<=1000,m<=50
对于100%的数据n<=10000,m<=100,c<=10000,K<=10000000
分子树计算，避免重复，标记一下即可，如果k过大，但是m较小，离散化一下即可。
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=21000;
const int maxx=10000010;
const int inf=0x3f3f3f3f;
int head[maxn],ver[maxn],edge[maxn],nt[maxn];
int max_part[maxn],_size[maxn],query[maxn];
bool ha[maxn],is_ha[maxx],last[maxn];
int use[maxn];
int tot=1,root,max_size,ans=0,n,m,k;
vector<int>dis;
void init(void)
{
memset(head,0,sizeof(head));
memset(ha,0,sizeof(ha));
memset(last,0,sizeof(last));
tot=1,ans=0;
}
void add(int x,int y,int z)
{
ver[++tot]=y,edge[tot]=z;
nt[tot]=head[x],head[x]=tot;
}
void dfs_size(int x,int fa)
{
_size[x]=1,max_part[x]=0;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(ha[y]||y==fa) continue;
dfs_size(y,x);
_size[x]+=_size[y];
max_part[x]=max(max_part[x],_size[y]);
}
}
void dfs_root(int now_root,int x,int fa)
{
max_part[x]=max(max_part[x],_size[now_root]-_size[x]);
if(max_size>max_part[x])
{
max_size=max_part[x];
root=x;
}
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(ha[y]||y==fa) continue;
dfs_root(now_root,y,x);
}
}
void dfs_dis(int x,int fa,int diss)
{
dis.push_back(diss);
for(int i=head[x];i;i=nt[i])
{
int y=ver[i],z=edge[i];
if(ha[y]||y==fa) continue;
dfs_dis(y,x,diss+z);
}
}
void get_num(int x)
{
is_ha[0]=true;
int cnt=0;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i],z=edge[i];
if(ha[y]) continue;
dis.clear();
dfs_dis(y,x,z);
for(int j=0;j<dis.size();j++)
{
for(int k=1;k<=m;k++)
{
if(query[k]>=dis[j])
last[k]|=is_ha[query[k]-dis[j]];
}
}
for(int j=0;j<dis.size();j++)
use[++cnt]=dis[j],is_ha[dis[j]]=true;
}
for(int i=1;i<=cnt;i++)
is_ha[use[i]]=false;
}
void dfs(int x)
{
max_size=inf;
dfs_size(x,-1);
dfs_root(x,x,-1);
get_num(root);
ha[root]=1;
for(int i=head[root];i;i=nt[i])
{
int y=ver[i],z=edge[i];
if(ha[y]) continue;
dfs(y);
}
}
int main(void)
{
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
int x,y,z;
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);add(y,x,z);
}
for(int i=1;i<=m;i++)
{
scanf("%d",&query[i]);
}
dfs(1);
for(int i=1;i<=m;i++)
{
if(last[i]) printf("AYE\n");
else printf("NAY\n");
}
}
return 0;
}
二、边分治。
①：
题目描述
给出一棵边带权的节点数量为n的树，初始树上所有节点都是白色。有两种操作：
C x，改变节点x的颜色，即白变黑，黑变白
A，询问树中最远的两个白色节点的距离，这两个白色节点可以重合(此时距离为0)。
输入格式
In the first line there is an integer N (N <= 100000)
In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of value c (-1000 <= c <= 1000)
In the next line, there is an integer Q denotes the number of instructions (Q <= 200000)
In the next Q lines, each line contains an instruction “C a” or “A”
输出格式
For each “A” operation, write one integer representing its result. If there is no white node in the tree, you should write “They have disappeared.”.
输入输出样例
输入 #1 复制
3
1 2 1
1 3 1
7
A
C 1
A
C 2
A
C 3
A
输出 #1 复制
2
2
0
They have disappeared.
边分治，玄学时间复杂度，玄学空间复杂度。
重构树节点开正常两倍大小就可以，但是重构树之后的表示连接关系的有向树需要开大一点。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int maxn=200100;
int head[maxn],ver[maxn*20],edge[maxn*20],nt[maxn*20];
int Head[maxn],Ver[maxn<<1],Edge[maxn<<1],Nt[maxn<<1],tail[maxn],pre[maxn*20];
int d[maxn];
bool ha[maxn];
int nown,n,tot,TOT,root,midedge,maxx,cnt;
void init(void)
{
memset(head,0,sizeof(head));
tot=1;
}
void Init(void)
{
memset(Head,0,sizeof(Head));
TOT=1;
}
void add(int x,int y,int z)
{
ver[++tot]=y,edge[tot]=z;
nt[tot]=head[x],head[x]=tot;
}
void Add(int x,int y,int z)
{
Ver[++TOT]=y,Edge[TOT]=z;
Nt[TOT]=Head[x],Head[x]=TOT;
}
void get_pre(void)
{
memset(tail,0,sizeof(tail));
for(int x=1;x<=nown;x++)
{
for(int i=Head[x];i;i=Nt[i])
{
pre[i]=tail[x];
tail[x]=i;
}
}
}
void del(int x,int i)
{
if(Head[x]==i) Head[x]=Nt[i];
else Nt[pre[i]]=Nt[i];
if(tail[x]==i) tail[x]=pre[i];
else pre[Nt[i]]=pre[i];
}
void build(int x,int fa)
{
int now=0;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i],z=edge[i];
if(y==fa) continue;
if(!now)
{
Add(x,y,z),Add(y,x,z);
now=x;
}
else
{
ha[++nown]=false;
Add(nown,now,0),Add(now,nown,0);
Add(y,nown,z),Add(nown,y,z);
now=nown;
}
build(y,x);
}
}
void rebuild(void)
{
Init();
nown=n;
for(int i=1;i<=nown;i++) ha[i]=1;
build(1,0);
get_pre();
init();
}
struct point
{
int y;
int dis;
point(){}
point(int a,int b)
{
y=a,dis=b;
}
friend bool operator <(const point &a,const point &b)
{
return a.dis<b.dis;
}
};
struct node
{
int root,midlen,ans;
int lson,rson;
priority_queue<point>q;
}t[maxn<<1];
void _init(void)
{
for(int i=1;i<maxn<<2;i++)
{
while(t[i].q.size())
t[i].q.pop();
t[i].lson=t[i].rson=0;
}
cnt=1;
}
void dfs_size(int x,int fa,int dis)
{
add(x,root,dis);
if(ha[x]) t[root].q.push(point(x,dis));
d[x]=1;
for(int i=Head[x];i;i=Nt[i])
{
int y=Ver[i],z=Edge[i];
if(y==fa) continue;
dfs_size(y,x,dis+z);
d[x]+=d[y];
}
}
void dfs_midedge(int x,int nowi)
{
if(max(d[x],d[t[root].root]-d[x])<maxx)
{
maxx=max(d[x],d[t[root].root]-d[x]);
midedge=nowi;
}
for(int i=Head[x];i;i=Nt[i])
{
int y=Ver[i];
if(i!=(nowi^1)) dfs_midedge(y,i);
}
}
void pushup(int id)
{
t[id].ans=-1;
while(t[id].q.size()&&ha[t[id].q.top().y]==0) t[id].q.pop();
int lson=t[id].lson,rson=t[id].rson;
if(lson==0&&rson==0)
{
if(ha[t[id].root]) t[id].ans=0;
}
else
{
if(t[lson].ans>t[id].ans) t[id].ans=t[lson].ans;
if(t[rson].ans>t[id].ans) t[id].ans=t[rson].ans;
if(t[lson].q.size()&&t[rson].q.size())
t[id].ans=max(t[id].ans,t[lson].q.top().dis+t[rson].q.top().dis+t[id].midlen);
}
}
void dfs(int id,int x)
{
root=id,maxx=nown,midedge=0;
t[id].root=x;
dfs_size(x,0,0);
dfs_midedge(x,0);
if(midedge)
{
int p1=Ver[midedge];
int p2=Ver[midedge^1];
t[id].midlen=Edge[midedge];
t[id].lson=++cnt;
t[id].rson=++cnt;
del(p1,midedge^1);
del(p2,midedge);
dfs(t[id].lson,p1);
dfs(t[id].rson,p2);
}
pushup(id);
}
void update(int x)
{
ha[x]^=1;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i],z=edge[i];
if(ha[x]==1) t[y].q.push(point(x,z));
pushup(y);
}
}
int main(void)
{
while(scanf("%d",&n)!=EOF)
{
init();
//_init();
cnt=1;
int x,y,z;
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
rebuild();
dfs(1,1);
char str[20];
int m,pos;
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%s",str);
if(str[0]=='A')
{
if(t[1].ans==-1) printf("They have disappeared.\n");
else printf("%d\n",t[1].ans);
}
else
{
scanf("%d",&pos);
update(pos);
}
}
}
return 0;
}
②：题目描述
Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由N个屋子和N-1条双向走廊组成，这N-1条走廊的分布使得任意两个屋子都互相可达。
游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这N个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，Jiajia希望知道可能的最远的两个孩子的距离（即最远的两个关灯房间的距离）。
我们将以如下形式定义每一种操作：
C(hange) i 改变第i个房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。
G(ame) 开始一次游戏，查询最远的两个关灯房间的距离。
输入格式
第一行包含一个整数N，表示房间的个数，房间将被编号为1,2,3…N的整数。
接下来N-1行每行两个整数a, b，表示房间a与房间b之间有一条走廊相连。
接下来一行包含一个整数Q，表示操作次数。接着Q行，每行一个操作，如上文所示。
输出格式
对于每一个操作Game，输出一个非负整数到hide.out，表示最远的两个关灯房间的距离。若只有一个房间是关着灯的，输出0；若所有房间的灯都开着，输出-1。
输入输出样例
输入 #1 复制
8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
7
G
C 1
G
C 2
G
C 1
G
输出 #1 复制
4
3
3
4
说明/提示
对于20%的数据， N ≤50, M ≤100；
对于60%的数据， N ≤3000, M ≤10000； 对于100%的数据， N ≤100000, M ≤500000。
洛谷O2大法好。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int maxn=200100;
int head[maxn],ver[maxn*20],edge[maxn*20],nt[maxn*20];
int Head[maxn],Ver[maxn<<1],Edge[maxn<<1],Nt[maxn<<1],tail[maxn],pre[maxn*20];
int d[maxn];
bool ha[maxn];
int nown,n,tot,TOT,root,midedge,maxx,cnt;
void init(void)
{
memset(head,0,sizeof(head));
tot=1;
}
void Init(void)
{
memset(Head,0,sizeof(Head));
TOT=1;
}
void add(int x,int y,int z)
{
ver[++tot]=y,edge[tot]=z;
nt[tot]=head[x],head[x]=tot;
}
void Add(int x,int y,int z)
{
Ver[++TOT]=y,Edge[TOT]=z;
Nt[TOT]=Head[x],Head[x]=TOT;
}
void get_pre(void)
{
memset(tail,0,sizeof(tail));
for(int x=1;x<=nown;x++)
{
for(int i=Head[x];i;i=Nt[i])
{
pre[i]=tail[x];
tail[x]=i;
}
}
}
void del(int x,int i)
{
if(Head[x]==i) Head[x]=Nt[i];
else Nt[pre[i]]=Nt[i];
if(tail[x]==i) tail[x]=pre[i];
else pre[Nt[i]]=pre[i];
}
void build(int x,int fa)
{
int now=0;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i],z=edge[i];
if(y==fa) continue;
if(!now)
{
Add(x,y,z),Add(y,x,z);
now=x;
}
else
{
ha[++nown]=false;
Add(nown,now,0),Add(now,nown,0);
Add(y,nown,z),Add(nown,y,z);
now=nown;
}
build(y,x);
}
}
void rebuild(void)
{
Init();
nown=n;
for(int i=1;i<=nown;i++) ha[i]=1;
build(1,0);
get_pre();
init();
}
struct point
{
int y;
int dis;
point(){}
point(int a,int b)
{
y=a,dis=b;
}
friend bool operator <(const point &a,const point &b)
{
return a.dis<b.dis;
}
};
struct node
{
int root,midlen,ans;
int lson,rson;
priority_queue<point>q;
}t[maxn<<1];
void _init(void)
{
for(int i=1;i<maxn<<2;i++)
{
while(t[i].q.size())
t[i].q.pop();
t[i].lson=t[i].rson=0;
}
cnt=1;
}
void dfs_size(int x,int fa,int dis)
{
add(x,root,dis);
if(ha[x]) t[root].q.push(point(x,dis));
d[x]=1;
for(int i=Head[x];i;i=Nt[i])
{
int y=Ver[i],z=Edge[i];
if(y==fa) continue;
dfs_size(y,x,dis+z);
d[x]+=d[y];
}
}
void dfs_midedge(int x,int nowi)
{
if(max(d[x],d[t[root].root]-d[x])<maxx)
{
maxx=max(d[x],d[t[root].root]-d[x]);
midedge=nowi;
}
for(int i=Head[x];i;i=Nt[i])
{
int y=Ver[i];
if(i!=(nowi^1)) dfs_midedge(y,i);
}
}
void pushup(int id)
{
t[id].ans=-1;
while(t[id].q.size()&&ha[t[id].q.top().y]==0) t[id].q.pop();
int lson=t[id].lson,rson=t[id].rson;
if(lson==0&&rson==0)
{
if(ha[t[id].root]) t[id].ans=0;
}
else
{
if(t[lson].ans>t[id].ans) t[id].ans=t[lson].ans;
if(t[rson].ans>t[id].ans) t[id].ans=t[rson].ans;
if(t[lson].q.size()&&t[rson].q.size())
t[id].ans=max(t[id].ans,t[lson].q.top().dis+t[rson].q.top().dis+t[id].midlen);
}
}
void dfs(int id,int x)
{
root=id,maxx=nown,midedge=0;
t[id].root=x;
dfs_size(x,0,0);
dfs_midedge(x,0);
if(midedge)
{
int p1=Ver[midedge];
int p2=Ver[midedge^1];
t[id].midlen=Edge[midedge];
t[id].lson=++cnt;
t[id].rson=++cnt;
del(p1,midedge^1);
del(p2,midedge);
dfs(t[id].lson,p1);
dfs(t[id].rson,p2);
}
pushup(id);
}
void update(int x)
{
ha[x]^=1;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i],z=edge[i];
if(ha[x]==1) t[y].q.push(point(x,z));
pushup(y);
}
}
int main(void)
{
while(scanf("%d",&n)!=EOF)
{
init();
//_init();
cnt=1;
int x,y;
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y,1);
add(y,x,1);
}
rebuild();
dfs(1,1);
char str[20];
int m,pos;
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%s",str);
if(str[0]=='G')
{
printf("%d\n",t[1].ans);
}
else
{
scanf("%d",&pos);
update(pos);
}
}
}
return 0;
}
三、动态点分治：
以后再学吧。。。。
京公网安备 11010502036488号