Before the content
很多好题
收获颇丰
something of dfs序
概念：在对树进行深度优先遍历时,对于每个节点,在刚进入递归后以及即将回溯前记录一次该点的编号，最后产生的长度为2*N的节点序列就称为树的dfs序
void dfs(int x) { a[++m]=x; v[x]=1; for (int i=h[x];~i;i=nex[i]) { int j=ver[i]; if(v[j]) continue; dfs(j); } a[++m]=x; }特点：你可以把他理解为一个时间戳，相当于通过每一个点被遍历到的顺序将这棵树拉成了一条链。每一个节点在序列中恰好出现了两次(当然,有时只需要记录一次),设为
,那么以闭区间
就是以x为根的子树的dfs序,当然，我更多采用的是记录x子树中的节点数，那么[
]就是他子树的dfs序区间
经典用法：
- 配合树状数组进行区间修改，单点查询
- 用于树链剖分进行更多的操作
- 树上莫队
- 更多的靠做题发现(我只会这么多QwQ)
例题
Military Problem
题意：给出n-1对关系(构成一棵树),q个询问,包含
,表示一个命令从u点下达,问在他的子树中第v个收到命令的节点编号
分析：不是才学完dfs序吗？在这颗子树中，第v个收到命令的那就是dfs序为
的节点
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1e3;
int n,q,tot,cnt;
int dfn[N],id[N],siz[N];
vector<int>g[N];
inline void dfs(int u)
{
dfn[u]=++cnt;
id[cnt]=u;
siz[u]=1;
int len=g[u].size();
for (int i=0;i<len;i++)
{
int j=g[u][i];
dfs(j);
siz[u]+=siz[j];
}
}
int main()
{
scanf("%d%d",&n,&q);
for (int i=2,x;i<=n;i++)
scanf("%d",&x),g[x].push_back(i);
dfs(1);
while(q--)
{
int u,k;
scanf("%d%d",&u,&k);
if(siz[u]<k) puts("-1");
else printf("%d\n",id[dfn[u]+k-1]);
}
return 0;
}选点
分析：题目中说，如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大；如果在左子树选了一个点，在右子树中选的其他点要比它小。如果我们把这颗树拉成一条链，根据规律左节点>右节点>根节点，相当于在这个序列上求出一个最长下降子序列。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,cnt,tot;
int ch[2][N],a[N],f[N],k[N];
inline void dfs(int u)
{
if(!u) return ;
a[++tot]=k[u];
dfs(ch[1][u]);
dfs(ch[0][u]);
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&k[i]);
for (int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
ch[0][i]=x,ch[1][i]=y;
}
dfs(1);
f[++cnt]=a[1];
for (int i=2;i<=n;i++)
{
if(a[i]>f[cnt]) f[++cnt]=a[i];
else
{
int pos=lower_bound(f+1,f+cnt+1,a[i])-f;
f[pos]=a[i];
}
}
printf("%d\n",cnt);
return 0;
}Tree Requests
题意：给出一棵树，树上的每一个节点都有一个对应的字符。定义一个节点的深度为节点到根节点1的路径上点的数量。有m个询问，每次包含一个
分析：我发现他结合了两道题，大家有兴趣可以去看看:小睿睿的兄弟 & Hyperdrome同时附上我的题解题1&题2。然后让我们步入正题，判断他能否构成一个回文串，我只需要状态压缩每一个字母的个数，然后通过dfs序，通过二分求出在第v层中属于子树u的节点(题二解法)，再通过前缀和，判断是否合法(题一解法)。这种结合，也许就是算法的美妙。避免了麻烦的树剖。
#include<bits/stdc++.h>
#define inf 1e9
using namespace std;
const int N=5e5+10;
int n,tot,m,cnt,dt;
int h[N],nex[N],ver[N];
int id[N],dfn[N],siz[N],dep[N],a[N];
char k[N];
vector<int>g[N],f[N];
inline void add(int x,int y)
{
nex[tot]=h[x];
ver[tot]=y;
h[x]=tot++;
}
inline void dfs(int u,int v)
{
dep[u]=dep[v]+1;dt=max(dt,dep[u]);
dfn[u]=++cnt,id[cnt]=u;siz[u]=1;
g[dep[u]].push_back(cnt);
for (int i=h[u];~i;i=nex[i])
{
int j=ver[i];
if(j==v) continue;
dfs(j,u);
siz[u]+=siz[j];
}
}
int main()
{
memset(h,-1,sizeof(h));
scanf("%d%d",&n,&m);
for (int i=2,x;i<=n;i++)
scanf("%d",&x),add(x,i);
dfs(1,0);
scanf("%s",k);
for (int i=1;i<=n;i++) a[i]=k[i-1]-'a';
for (int i=1;i<=dt;i++)
{
int len=g[i].size();
int now=0;
f[i].push_back(0);
for (int j=0;j<len;j++)
{
now^=(1<<(a[id[g[i][j]]]));
f[i].push_back(now);
}//dfs序肯定是连续的
g[i].push_back(inf);
}
int x,y,xx,yy,l,r;
while(m--)
{
scanf("%d%d",&x,&y);
//输入子树和深度
if(y>dt)
{
puts("Yes");
continue;
}
l=0,r=g[y].size()-1,xx=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(g[y][mid]<dfn[x]) l=mid+1;
else r=mid-1,xx=mid;
}
l=0,r=g[y].size()-1,yy=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(g[y][mid]<=dfn[x]+siz[x]-1) l=mid+1;
else r=mid-1,yy=mid;
}//二分求出在第y层中属于子树u的节点的dfs序范围
if(xx<0||yy<0)
{
puts("Yes");
continue;
}//不存在
int ans=(f[y][yy]^f[y][xx]);
int up=0;
while(ans) up++,ans-=(ans&(-ans));
if(up<=1) puts("Yes");
else puts("No");
}
return 0;
}求和
分析：先引用一下上面那一张图
可以确定，每一刻子树中的dfs序是连续的。那么我们就在dfs序上建立一棵线段树，对于操作一，单点修改，对于操作二，区间查询
#include<bits/stdc++.h>
#define R register
#define ll long long
#define inf INT_MAX
#define ls now<<1
#define rs now<<1|1
using namespace std;
const int N=1e6+10;
int n,m,k,tot,cnt;
int h[N],nex[N<<1],ver[N<<1];
int val[N],dfn[N],id[N],siz[N],w[N],s[N<<2];
inline void add(int x,int y)
{
nex[tot]=h[x];
ver[tot]=y;
h[x]=tot++;
}
inline void dfs(int u,int v)
{
dfn[u]=++cnt;id[cnt]=u;
w[cnt]=val[u];siz[u]=1;
for (int i=h[u];~i;i=nex[i])
{
int j=ver[i];
if(j==v) continue;
dfs(j,u);
siz[u]+=siz[j];
}
}
inline void build(int now,int l,int r)
{
if(l==r)
{
s[now]=w[l];
return ;
}
int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
s[now]=s[ls]+s[rs];
}
inline void add(int now,int l,int r,int x,int v)
{
s[now]+=v;
if(l==r) return ;
int mid=(l+r)>>1;
if(x<=mid) add(ls,l,mid,x,v);
else add(rs,mid+1,r,x,v);
}
inline int find(int now,int l,int r,int x,int y)
{
if(l>=x&&r<=y) return s[now];
int mid=(l+r)>>1,ret=0;
if(x<=mid) ret+=find(ls,l,mid,x,y);
if(mid<y) ret+=find(rs,mid+1,r,x,y);
return ret;
}
int main()
{
memset(h,-1,sizeof(h));
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=n;i++) scanf("%d",&val[i]);
for (int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
dfs(k,0);build(1,1,n);
int opt,x,v;
while(m--)
{
scanf("%d%d",&opt,&x);
if(opt==2)
printf("%d\n",find(1,1,n,dfn[x],dfn[x]+siz[x]-1));
else
{
scanf("%d",&v);
add(1,1,n,dfn[x],v);
}
}
return 0;
}
Propagating tree
题意：给定一棵n个节点的树，它的根是1号节点。这棵树每个点都有一个权值，你需要完成这两种操作：
1. u val 表示给u节点的权值增加val
2. u 表示查询u节点的权值
它还有个神奇的性质：当某个节点的权值增加val时，它的子节点权值都增加-val，它子节点的子节点增加-(-val)...... 如此一直进行到树的底部。
分析：可以发现,奇数层会增加的权值相同,偶数层增加的权值相同,那用两个树状数组维护一下奇数层与偶数层。但是想一想,能否通过一个树状数组维护这个结果。因为对权值的加减只与节点的深度有关。先不考虑符号，通过差分就能实现区间修改,单点查询。
把深度加入考虑
1.如果当前的u节点的深度是奇数,那么其下的所有子节点，奇数层+相同权值,偶数层-相同权值
2.如果当前的u节点的深度是偶数,那么其下的所有子节点，奇数层-相同权值,偶数层+相同权值
但是他们的初值是不变的，只需要决定修改的值的正负就好
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int N=2e5+10;
int n,m,tot,idx;
bool vis[N];
int st[N],k[N],dep[N],ed[N];
int h[N],nex[N<<1],ver[N<<1],val[N];
inline void add(int x,int y)
{
nex[idx]=h[x];
ver[idx]=y;
h[x]=idx++;
}
inline void dfs(int u,int pre)
{
st[u]=++tot;
dep[u]=dep[pre]+1;vis[u]=1;
for (int i=h[u];~i;i=nex[i])
if(!vis[ver[i]])
dfs(ver[i],u);
ed[u]=tot;
}
inline int lowbit(int x)
{
return x&(-x);
}
inline void akd(int x,int y)
{
while(x<=tot)
{
k[x]+=y;
x+=lowbit(x);
}
}
inline int find(int x)
{
int res=0;
while(x)
{
res+=k[x];
x-=lowbit(x);
}
return res;
}
int main()
{
memset(h,-1,sizeof(h));
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&val[i]);
int x,y,z;
for (int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
dfs(1,0);
int ans=0;
while(m--)
{
scanf("%d%d",&x,&y);
if(x==1)
{
scanf("%d",&z);
if(dep[y]&1) akd(st[y],z),akd(ed[y]+1,-z);
else akd(st[y],-z),akd(ed[y]+1,z);
}
else
{
ans=find(st[y]);
if(dep[y]&1) ans=val[y]+ans;
else ans=val[y]-ans;
printf("%d\n",ans);
}
}
return 0;
}
京公网安备 11010502036488号