每日一题 dfs序专题 总结
Military Problem
简单题，我们预处理出dfs序，然后查询的时候之间判断一下sz的大小，就可以了！
代码：
#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
using namespace std;
inline int read(){
int nm=0,fh=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
return nm*fh;
}
#define M 200020
int n,q,dfn[M],cnt,rev[M],sz[M]; vector<int>vec[M];
inline void dfs(int u){
dfn[u]=++cnt,rev[cnt]=u,sz[u]=1;
for(int i=0,TP=vec[u].size();i<TP;i++) dfs(vec[u][i]),sz[u]+=sz[vec[u][i]];
}
int main(){
n=read(),q=read();
for(int i=2;i<=n;i++){int x=read(); vec[x].pb(i);}
for(int i=1;i<=n;i++) sort(vec[i].begin(),vec[i].end());
dfs(1);
while(q--){
int x=read(),k=read();
if(sz[x]<k) puts("-1"); else printf("%d\n",rev[dfn[x]+k-1]);
}
return 0;
}选点
这道题是一个好题，思路非常妙，我们考虑假设我们在树上选了若干个点，然后我们按照着题目给出的大小关系去dfs，然后这个dfs序是单调增的，同时这个选出来的权值也是单调增的，这样就可以启发我们直接搞出dfs序，然后哦根据dfs序求出新的val，然后针对这个序列求一个最长上升子序列就可以了！
这个思路非常新颖，我们在类似的选点问题也可以采用一样的办法。
代码：
#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
using namespace std;
inline int read(){
int nm=0,fh=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
return nm*fh;
}
#define M 100020
int n,val[M],ls[M],rs[M],a[M],cnt,sta[M],top;
inline void dfs(int u){
a[++cnt]=val[u];
if(rs[u]) dfs(rs[u]); if(ls[u]) dfs(ls[u]);
}
int main(){
n=read();
for(int i=1;i<=n;i++) val[i]=read();
for(int i=1;i<=n;i++) ls[i]=read(),rs[i]=read();
dfs(1);
for(int i=1;i<=n;i++){
if(!top||a[i]>sta[top]){sta[++top]=a[i]; continue;}
int pos=lower_bound(sta+1,sta+top+1,a[i])-sta;
sta[pos]=a[i];
} printf("%d\n",top);
return 0;
}
Colorful Tree
这题要求你求生成树的大小，我们发现这个大小问题其实和https://www.luogu.com.cn/problem/P3320寻宝游戏
这道题很像只是这道题从第一个点走到最后一个点，再回来，那么容易发先每条边都被走过两遍，对于这道题我们把最后的结果除以2就可以了，
我们针对每种颜色分别维护一下，支持插入和删除，修改的时候先删除再插入即可，注意需要注意空集的特判。
代码：
#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
using namespace std;
inline int read(){
int nm=0,fh=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
return nm*fh;
}
#define M 100020
int n,tot,q,a[M],to[M<<1],nt[M<<1],fs[M];
int dep[M],fa[M][21],dfn[M],cnt,rev[M];
inline void link(int x,int y){to[++tot]=y,nt[tot]=fs[x],fs[x]=tot;}
inline int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=20;~i;i--) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
for(int i=20;~i;i--) if(fa[x][i]^fa[y][i]) x=fa[x][i],y=fa[y][i];
return (x==y)?x:fa[x][0];
}
inline int getdis(int x,int y){return dep[x]+dep[y]-(dep[lca(x,y)]<<1);}
inline void dfs(int x,int last=0){
dep[x]=dep[last]+1,dfn[x]=++cnt,rev[cnt]=x,fa[x][0]=last;
for(int i=1;i<=20;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=fs[x];i;i=nt[i]) if(to[i]^last) dfs(to[i],x);
}
#define IT set<int>::iterator
struct Sol{
set<int>s; LL all;
inline int fdnxt(int x){
if(s.empty()) return -1;
IT it=s.upper_bound(x);
return (it==s.end())?-1:rev[*it];
}
inline int fdpre(int x){
if(s.empty()) return -1;
IT it=s.lower_bound(x); return (it==s.begin())?-1:rev[*(--it)];
}
inline void Ins(int x){
int pos=dfn[x],nx=fdnxt(pos),px=fdpre(pos);
if((~nx)&&(~px)) all-=(LL)getdis(nx,px);
if(~nx) all+=(LL)getdis(nx,x);
if(~px) all+=(LL)getdis(px,x);
s.insert(pos);
}
inline void Del(int x){
int pos=dfn[x],nx=fdnxt(pos),px=fdpre(pos);
if((~nx)&&(~px)) all+=(LL)getdis(nx,px);
if(~nx) all-=(LL)getdis(nx,x);
if(~px) all-=(LL)getdis(px,x);
s.erase(pos);
}
inline LL gtans(){
if(s.empty()) return -1ll;
return (all+getdis(rev[*s.begin()],rev[*s.rbegin()]))/2ll;
}
inline void debug(){
for(IT it=s.begin();it!=s.end();it++)
printf("%d ",*it);
printf("\n");
}
}P[M];
int main(){
n=read();
for(int i=1,x,y;i<n;i++) x=read(),y=read(),link(x,y),link(y,x);
dfs(1); for(int i=1;i<=n;i++) a[i]=read(),P[a[i]].Ins(i);
q=read();
while(q--){
char op[15]; scanf("%s",op);
if(op[0]=='U'){
int x=read(),y=read();
P[a[x]].Del(x),a[x]=y,P[a[x]].Ins(x);
} else{int x=read(); printf("%lld\n",P[x].gtans());}
//for(int i=1;i<=3;i++) P[i].debug();
}
return 0;
}
Tree Requests
一道处理子树内部的问题，子树内部的处理通常我们需要用dfs序，然后如果可以离线我们可以用分治，莫队等算法在dfs序上进行，强制在线可以用一些主席树线段树分块等算法。
但是看到这道题，我写了一个和dfs序没有太大关系的dsu on the tree（之后作者应该会写一个dsu on the tree的总结）
然后我们可以用二进制优化，具体我们可以见代码
代码：
#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
using namespace std;
inline int read(){
int nm=0,fh=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
return nm*fh;
}
#define M 500020
#define pii pair<int,int>
#define mp make_pair
#define fr first
#define sc second
int n,q,tot,to[M<<1],nt[M<<1],fs[M],ans[M];
int fa[M],dep[M],sz[M],mxs[M],hv[M],typ;
char ch[M]; vector<pii >vec[M];
inline void link(int u,int v){to[++tot]=v,nt[tot]=fs[u],fs[u]=tot;}
inline void dfs(int u){
dep[u]=dep[fa[u]]+1,sz[u]=1;
for(int i=fs[u];i;i=nt[i]) if(to[i]^fa[u]){
dfs(to[i]),sz[u]+=sz[to[i]];
if(sz[to[i]]>sz[mxs[u]]) mxs[u]=to[i];
}
}
inline void chg(int u,int Lim){
if(typ==-1) hv[dep[u]]=0; else hv[dep[u]]^=(1<<(ch[u]-'a'));
for(int i=fs[u];i;i=nt[i]) if((to[i]^fa[u])&&(to[i]^Lim)) chg(to[i],Lim);
}
inline bool Judge(int x){return __builtin_popcount(x)<2;}
inline void dfst(int u,int flag=0){
for(int i=fs[u];i;i=nt[i]) if((to[i]^fa[u])&&(to[i]^mxs[u])) dfst(to[i],1);
if(mxs[u]) dfst(mxs[u],0);
typ=1,chg(u,mxs[u]);
for(int i=0,TP=vec[u].size();i<TP;i++) ans[vec[u][i].sc]=Judge(hv[vec[u][i].fr]);
if(flag) typ=-1,chg(u,0);
}
int main(){
n=read(),q=read();
for(int i=2;i<=n;i++) fa[i]=read(),link(fa[i],i);
scanf("%s",ch+1),dfs(1);
for(int i=1;i<=q;i++){
int x=read(),y=read();
vec[x].pb(mp(y,i));
} dfst(1);
for(int i=1;i<=q;i++) puts(ans[i]?"Yes":"No");
return 0;
}
求和
一道裸题，我们直接树状数组的基本操作放到dfs序上就可以了
#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
using namespace std;
inline int read(){
int nm=0,fh=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
return nm*fh;
}
#define M 1000020
int n,m,rt,val[M],tot,to[M<<1],nt[M<<1],fs[M],L[M],R[M],cnt; LL sum[M];
inline void link(int u,int v){to[++tot]=v,nt[tot]=fs[u],fs[u]=tot;}
inline void dfs(int u,int last=0){
L[u]=++cnt;
for(int i=fs[u];i;i=nt[i]) if(to[i]^last) dfs(to[i],u);
R[u]=cnt;
}
inline void mdf(int x,int y){for(int i=x;i<=n;i+=(i&-i)) sum[i]+=(LL)y;}
inline LL qry(int x,int y){
LL ret=0;
for(int i=y;i;i-=(i&-i)) ret+=sum[i];
for(int i=x-1;i;i-=(i&-i)) ret-=sum[i];
return ret;
}
int main(){
n=read(),m=read(),rt=read();
for(int i=1;i<=n;i++) val[i]=read();
for(int i=1;i<n;i++){int u=read(),v=read(); link(u,v),link(v,u);}
dfs(rt); for(int i=1;i<=n;i++) mdf(L[i],val[i]);
while(m--){
int opt=read(),x=read();
if(opt==1){int y=read(); mdf(L[x],y);}
else printf("%lld\n",qry(L[x],R[x]));
}
return 0;
}
Propagating tree
其实这道题的思维难度并不高，
这道题的操作虽然感觉很麻烦，但是发现它操作的本质无非就是对于奇偶分别讨论，就这么两种情况，那么我们针对奇偶分别维护一个树状数组就可以了，和上面的题感觉本质差不多。
代码：
#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
using namespace std;
inline int read(){
int nm=0,fh=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
return nm*fh;
}
#define M 200020
int n,m,tot,to[M<<1],nt[M<<1],fs[M],a[M],L[M],R[M],cnt,dep[M];
inline void link(int u,int v){to[++tot]=v,nt[tot]=fs[u],fs[u]=tot;}
inline void dfs(int u,int last=0){
L[u]=++cnt,dep[u]=dep[last]+1;
for(int i=fs[u];i;i=nt[i]) if(to[i]^last) dfs(to[i],u);
R[u]=cnt;
}
struct BIT{
int sum[M];
inline void mdf(int x,int y){for(int i=x;i<=n;i+=(i&-i)) sum[i]+=y;}
inline int qry(int x){int ret=0; for(int i=x;i;i-=(i&-i)) ret+=sum[i]; return ret;}
}P[2];
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<n;i++){int u=read(),v=read(); link(u,v),link(v,u);}
dfs(1);
while(m--){
int opt=read(),x=read();
if(opt==1){
int y=read(),td=dep[x]&1;
P[td].mdf(L[x],y),P[td].mdf(R[x]+1,-y);
P[td^1].mdf(L[x],-y),P[td^1].mdf(R[x]+1,y);
}else printf("%d\n",P[dep[x]&1].qry(L[x])+a[x]);
}
return 0;
}
查看9道真题和解析
