洛谷 P4092 [HEOI2016/TJOI2016]树 题解【树链剖分】/【并查集】/【模拟】
点击量：82
虽然这题可以用树剖或并查集来做，不过裸奔是最快的。。。
题目描述
在2016年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树（根为1），有以下两种操作：
- 标记操作：对某个结点打上标记（在最开始，只有结点1有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。）
- 询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖先）
你能帮帮他吗?
输入输出格式
输入格式：
输入第一行两个正整数N和Q分别表示节点个数和操作次数
接下来N-1行，每行两个正整数u,v(1≤u,v≤n)表示u到v有一条有向边
接下来Q行，形如“opernum”oper为“C”时表示这是一个标记操作,oper为“Q”时表示这是一个询问操作对于每次询问操作。
输出格式：
输出一个正整数，表示结果
输入输出样例
输入样例#1：5 51 21 32 42 5Q 2C 2Q 2Q 5Q 3输出样例#1：1221说明
30%的数据，1 ≤ N, Q ≤ 1000
70%的数据，1 ≤ N, Q ≤ 10000
100%的数据，1 ≤ N, Q ≤ 100000
裸奔：
dfs把这棵树构建出来，然后染色，询问直接沿着链找父亲。理论复杂度$ N^2$，实际复杂度$ O(N) \le O(?) \le O(N\log N)$。下面贴代码。
树剖：
首先我们看到这是一棵有根树，并且节点的改变可能会影响到它的子树，因此我们考虑树链剖分。不过这个树剖是一个阉割版的树剖，因为它只有子树查询，节省了60%的树剖过程。
对于改变，我们只需要在线段树中添加一个判断，就是更新时对比，把答案改成深度较大的那一个。利用树剖的思想就可以做了。
并查集：
想出这种做法的人真的是神奇%%%，用离线并查集的方式来做这道题。思路：我们把所有的询问存起来，接着把所有需要染色的全部染色。预处理并查集存最近染色祖先，在dfs里可以完成。当修改时，将这个点的cnt（染色次数）–，当cnt为0时，将它的最近染色祖先更新到它父亲的find。处理时细节比较多，最后记得正序输出即可，真坑。
Code：时间实际复杂度从高到低排序
树剖
#include<cstdio>
#include<cstring>
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
#define Mid (t[k].l+t[k].r>>1)
struct edge
{
int n,nxt;
edge(int n,int nxt)
{
this->n=n;
this->nxt=nxt;
}
edge()
{
nxt=-1;
}
}e[210000];
int head[101000],Cnt=-1;
void add(int from,int to)
{
e[++Cnt]=edge(to,head[from]);
head[from]=Cnt;
}
int d[101000],dfn[101000],cnt=0,over[101000];
int dmax(int x,int y)//判断深度大小并返回较深的一个
{
return d[x]>d[y]?x:y;
}
void dfs(int x)
{
dfn[x]=++cnt;
for(int i=head[x];~i;i=e[i].nxt)
if(!dfn[e[i].n])
{
d[e[i].n]=d[x]+1;
dfs(e[i].n);
}
over[x]=cnt;
}
int n,m;
struct node
{
int l,r,v,lazy;
node(int l,int r,int v)
{
this->l=l;
this->r=r;
this->v=v;
lazy=0;
}
node(int l,int r)
{
this->l=l;
this->r=r;
v=0;
lazy=0;
}
node()
{
v=0;
lazy=0;
}
}t[410000];
void build(int k,int l,int r)
{
if(l==r)
{
t[k]=node(l,r,1);
return;
}
t[k]=node(l,r);
build(ls,l,mid);
build(rs,mid+1,r);
}
void pushdown(int k)
{
if(t[k].l==t[k].r||!t[k].lazy)//lazy稍微改动一点
return;
t[ls].v=dmax(t[k].lazy,t[ls].v);
t[ls].lazy=dmax(t[k].lazy,t[ls].lazy);
t[rs].v=dmax(t[k].lazy,t[rs].v);
t[rs].lazy=dmax(t[k].lazy,t[rs].lazy);
t[k].lazy=0;
return;
}
void change(int k,int l,int r,int x)
{
if(l==t[k].l&&r==t[k].r)
{
t[k].lazy=dmax(t[k].lazy,x);
t[k].v=dmax(t[k].lazy,x);
return;
}
pushdown(k);
if(r<=Mid)
change(ls,l,r,x);
else if(l>Mid)
change(rs,l,r,x);
else
{
change(ls,l,Mid,x);
change(rs,Mid+1,r,x);
}
}
int ask(int k,int x)
{
pushdown(k);
if(t[k].l==t[k].r)
return t[k].v;
if(x<=Mid)
return ask(ls,x);
else
return ask(rs,x);
}
int main()
{
d[0]=0;
int u,v,k;
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
d[1]=1;
dfs(1);
build(1,1,n);
char q;
for(int i=1;i<=m;i++)
{
scanf("\n");
q=getchar();
scanf("%d",&k);
if(q=='C')
change(1,dfn[k],over[k],k);//只管子树，不用真正树剖
else
printf("%d\n",ask(1,dfn[k]));
}
return 0;
}
裸奔：O(N²)（事实证明这比树剖快 不知道luogu会不会出数据卡掉）
#include<cstdio>
#include<cstring>
struct edge
{
int n,nxt;
edge(int n,int nxt)
{
this->n=n;
this->nxt=nxt;
}
edge()
{
nxt=-1;
}
}e[210000];
int head[101000],cnt=-1;
void add(int from,int to)
{
e[++cnt]=edge(to,head[from]);
head[from]=cnt;
}
int d[101000],fa[101000];
bool c[101000];
void dfs(int x)
{
for(int i=head[x];~i;i=e[i].nxt)
{
if(!d[e[i].n])
{
d[e[i].n]=d[x]+1;
fa[e[i].n]=x;//只用存个父亲就行了
dfs(e[i].n);
}
}
}
int ask(int x)
{
while(c[x]==0)
x=fa[x];
return x;
}
int main()
{
memset(d,0,sizeof(d));
memset(c,false,sizeof(c));
memset(head,-1,sizeof(head));
c[1]=true;
int n,m,u,v;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
fa[1]=0;
d[1]=1;
dfs(1);
char q;
int k;
for(int i=1;i<=m;i++)
{
scanf("\n%c%d",&q,&k);
if(q=='C')
c[k]=true;
else
printf("%d\n",ask(k));
}
return 0;
}
并查集：路径压缩理论O(N)维护，也是三种中最快的
#include<cstdio>
#include<cstring>
struct edge
{
int n,nxt;
edge(int n,int nxt)
{
this->n=n;
this->nxt=nxt;
}
edge()
{
nxt=-1;
}
}e[210000];
int head[110000],Cnt=-1;
void add(int from,int to)
{
e[++Cnt]=edge(to,head[from]);
head[from]=Cnt;
}
struct ask
{
char op;
int num,ans;
ask()
{
ans=0;
}
}q[110000];
int s[110000];
int cnt[110000];
int fa[110000];
void dfs(int x)
{
for(int i=head[x];~i;i=e[i].nxt)
if(e[i].n!=fa[x])
{
fa[e[i].n]=x;
if(cnt[e[i].n])//注意这里的细节
s[e[i].n]=e[i].n;
else
s[e[i].n]=s[x];
dfs(e[i].n);
}
}
int my_find(int x)
{
if(s[x]==x)
return x;
return s[x]=my_find(s[x]);
}
int main()
{
memset(head,-1,sizeof(head));
memset(cnt,0,sizeof(cnt));
int n,m,u,v;
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
s[i]=i;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
s[n]=n;
cnt[1]=1;
for(int i=1;i<=m;i++)
{
scanf("\n%c%d",&q[i].op,&q[i].num);
if(q[i].op=='C')
cnt[q[i].num]++;//提前计算
}
fa[1]=1;
cnt[1]++;
dfs(1);//dfs处理
for(int i=m;i>=1;i--)//倒着做
{
if(q[i].op=='Q')
q[i].ans=my_find(q[i].num);
else
{
cnt[q[i].num]--;
if(!cnt[q[i].num])
s[q[i].num]=fa[q[i].num];
}
}
for(int i=1;i<=m;i++)//正着输出
if(q[i].ans)
printf("%d\n",q[i].ans);
return 0;
}
说点什么