@[追梦之鲸](/user/361726) 不懂就问：dfn序是什么？
by heyx0201 @ 2023-12-13 22:28:25
@[heyx0201](/user/768951) 抱歉，打错了，是dfs序
by 追梦之鲸 @ 2023-12-13 22:30:08
@[追梦之鲸](/user/361726) 感谢您！
by cxlian25 @ 2024-03-02 12:30:27
@[追梦之鲸](/user/361726) 同志，请问这份代码也是只A#11，但是有什么问题呢？
```cpp
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define N (int)1e5+5
using namespace std;
int n,m,root=1,cnt,tot,a[N],head[N],dep[N],sz[N],son[N],id[N],top[N],fat[N];
ll na[N],tr[N<<2],la[N<<2];
struct Edge{
int u,v,nxt;
}e[N<<1];
inline void add(int u,int v){
e[++cnt]=Edge{u,v,head[u]};
head[u]=cnt;
}
inline void dfs1(int u,int fa){
dep[u]=dep[fa]+1;sz[u]=1;fat[u]=fa;
for(int i=head[u];i;i=e[i].nxt){
if(e[i].v==fa) continue;
dfs1(e[i].v,u);
sz[u]+=sz[e[i].v];
if(sz[e[i].v]>sz[son[u]]) son[u]=e[i].v;
}
}
inline void dfs2(int u,int fa){
id[u]=++tot,na[tot]=a[u];
if(son[u]) top[son[u]]=top[u],dfs2(son[u],u);
for(int i=head[u];i;i=e[i].nxt){
if(e[i].v==fa||e[i].v==son[u]) continue;
top[e[i].v]=e[i].v;
dfs2(e[i].v,u);
}
}
inline void pushup(int p){
tr[p]=tr[p<<1]+tr[p<<1|1];
}
inline void build(int l,int r,int p){
if(l==r){
tr[p]=1;
return ;
}
int m=(l+r)>>1;
build(l,m,p<<1);build(m+1,r,p<<1|1);
pushup(p);
}
inline void pushdown(int s,int t,int p){
int m=s+t>>1;
if(la[p]) tr[p<<1]=max(tr[p<<1],la[p]),tr[p<<1|1]=max(tr[p<<1|1],la[p]),la[p<<1]=max(la[p],la[p<<1]),la[p<<1]=max(la[p],la[p<<1]);
la[p]=0;
}
inline void update(int l,int r,int s,int t,int c,int p){
if(l<=s&&t<=r){
tr[p]=max(tr[p],(ll)c);
la[p]=max(tr[p],(ll)c);
return ;
}
pushdown(s,t,p);
int m=(s+t)>>1;
if(l<=m) update(l,r,s,m,c,p<<1);
if(r>m) update(l,r,m+1,t,c,p<<1|1);
pushup(p);
}
inline ll query(int l,int r,int s,int t,int p){
if(l<=s&&t<=r) return tr[p];
pushdown(s,t,p);
ll m=(s+t)>>1,v=0;
if(l<=m) v=query(l,r,s,m,p<<1);
if(r>m) v+=query(l,r,m+1,t,p<<1|1);
return v;
}
void update_tree(int u,int c){
update(id[u],id[u]+sz[u]-1,1,n,id[c],1);
}
ll query_path(int u,int v){
ll ans=0;
while(top[u]^top[v]){
if(dep[top[u]]<dep[top[v]]) u^=v^=u^=v;
ans+=query(id[top[u]],id[u],1,n,1);
u=fat[top[u]];
}
if(dep[u]<dep[v]) u^=v^=u^=v;
return (query(id[v],id[u],1,n,1)+ans);
}
signed main(){
cin>>n>>m;
for(int i=1,u,v;i<n;++i){
cin>>u>>v;add(u,v),add(v,u);
}
top[root]=root;
dfs1(root,0);
dfs2(root,0);
build(1,n,1);
while(m--){
char ss;
int x;
cin>>ss>>x;
if(ss=='C') update_tree(x,x);
else printf("%lld\n",query_path(x,x));
}
return 0;
}
```
by luo_xiaoran @ 2024-03-12 09:19:43
@[追梦之鲸](/user/361726) 不好意思，问题有点多，已解决。
by luo_xiaoran @ 2024-03-13 20:12:02
过了，感谢orzorz
by baka24 @ 2024-04-19 12:10:43