题解 P7735 【[NOI2021] 轻重边】
搞一个非常规的做法，用 LCT 的结构直接表示轻重边。
- 我们发现这个题目给出的操作十分像 LCT 的 access 操作，所以不免直接往这方面想。
- 我们要将一条链变为实链，常规的写法是换根到一个端点，再 access 另一个端点。这样可以取出我们的这条链来。
- 但是显然，在换根的时候我们调用了 access 一次，这次调用会直接让整个 LCT 与维护的轻重之间混乱，也就是说，我们不能使用换根操作。
- 考虑定根，如果要打通的一条链两个端点有父子关系，那是十分容易的。
- 考虑普遍情况，不妨设两个端点为 x 和 y 求出其 lca ，那么 lca 的两条重边都是连向儿子的。这也就是说 lca 一定没有连向父亲的重边，即 lca 一定是一条实链的链顶。
- 我们对于每个节点开一个“额外链” extra 表示它除了自己的实儿子是否有另外的向下的重边。这个 extra，容易发现只有每条实链的链顶的 extra 会有值。在 access 的时候直接清空就行了。
- 那么剩余部分的算法也大概出来了。我们每次打通一条实链，就是对于两个节点 lca 首先从实链分离，然后将两个儿子分别向上插实链直到最近公共祖先，记一边为实儿子，另一边记为额外链，将每个节点到根的重边数量按照 LCT 的结构改变直接维护出来。查询就是和 LCA 做差分即可。可以发现它没有破坏均摊分析。
- 然后就是一些细节的特判和实现细节，可以直接看代码。
//ayame保佑，夸哥保佑，狗妈保佑，MDR保佑，锉刀怪保佑，M99保佑，克爹保佑
#include<bits/stdc++.h>
using namespace std;
int p1=1000000,p2=0;
char buf[1000005],wb[1000005];
int gc() {
if(p1>=1000000)fread(buf,1,1000000,stdin),p1=0;
return buf[p1++];
}
#define gc getchar
#define Loli true
#define Kon xor true
long long getint() {
long long ret=0,flag=1;
char c=gc();
while(c<'0'||c>'9') {
if(c=='-')flag=-1;
c=gc();
}
while(c<='9'&&c>='0') {
ret=(ret<<3)+(ret<<1)+c-'0';
c=gc();
}
return ret*flag;
}
void pc(char x) {
if(p2>=1000000)fwrite(wb,1,1000000,stdout),p2=0;
wb[p2++]=x;
}
void wrt(long long x) {
if(x<0)pc('-'),x=-x;
int c[24]= {0};
if(!x)return pc('0'),void();
while(x)c[++c[0]]=x%10,x/=10;
while(c[0])pc(c[c[0]--]+'0');
}
int n,m;
vector<int> vec[100005];
int fa[100005],dep[100005];
int son[100005],sz[100005];
int tp[100005],rd[100005],cd[100005],sign;
int LCA(int x,int y){
while(tp[x]^tp[y]){
if(dep[tp[x]]<dep[tp[y]])swap(x,y);
x=fa[tp[x]];
}
if(dep[x]>dep[y])swap(x,y);
return x;
}
namespace T{
#define lowbit(i) (i&(-i))
int c[100005];
void clear(){
memset(c,0,sizeof(c));
}
void add(int pl,int val){
for(int i=pl;i<=100000;i+=lowbit(i))c[i]+=val;
}
void add(int l,int r,int val){
add(l,val),add(r+1,-val);
}
int ask(int pl){
int ret=0;
for(int i=pl;i;i-=lowbit(i))ret+=c[i];
return ret;
}
};
namespace LCT{
struct node{
int ch[2],fa,pre,suf,extra;
}v[100005];
bool isroot(int x){
return v[v[x].fa].ch[0]!=x&&v[v[x].fa].ch[1]!=x;
}
void push_up(int rt){
v[rt].pre=v[rt].ch[0]?v[v[rt].ch[0]].pre:rt;
v[rt].suf=v[rt].ch[1]?v[v[rt].ch[1]].suf:rt;
}
void init(){
T::clear();
for(int i=1;i<=100000;i++)v[i].ch[0]=v[i].ch[1]=v[i].fa=v[i].pre=v[i].suf=v[i].extra=0,push_up(i);
}
void rot(int x){
int p=v[x].fa,g=v[p].fa;
bool d=v[p].ch[1]==x;
if(!isroot(p))v[g].ch[v[g].ch[1]==p]=x;
v[p].ch[d]=v[x].ch[d^1];
v[v[x].ch[d^1]].fa=p;
v[x].ch[d^1]=p;
v[x].fa=g,v[p].fa=x;
push_up(p),push_up(x);
}
void splay(int x){
while(!isroot(x)){
int p=v[x].fa,g=v[p].fa;
if(!isroot(p))rot(v[g].ch[0]==p^v[p].ch[0]==x?x:p);
rot(x);
}
}
void ins(int x,int y){
if(!y)return;
T::add(rd[v[y].pre],cd[v[y].pre],-1);
}
void del(int x,int y){
if(!y)return;
T::add(rd[v[y].pre],cd[v[y].pre],1);
if(v[v[y].pre].extra)T::add(rd[v[v[y].pre].extra],cd[v[v[y].pre].extra],-1),v[v[y].pre].extra=0;
}
void split(int x){
splay(x);
if(v[fa[x]].extra==x)T::add(rd[x],cd[x],-1),v[fa[x]].extra=0;
if(v[x].extra)T::add(rd[v[x].extra],cd[v[x].extra],-1),v[x].extra=0;
if(!v[x].ch[0])return;
int y=v[v[x].ch[0]].suf;
splay(y),v[y].ch[1]=0,push_up(y);
T::add(rd[x],cd[x],-1);
}
void limit_access(int x,int Dep){
for(int y=0;x;y=x,x=v[x].fa){
splay(x),del(x,y),ins(x,v[x].ch[1]),v[x].ch[1]=y,push_up(x);
if(dep[v[x].pre]==Dep)return;
}
}
void expose(int x,int y){
if(dep[x]<dep[y])swap(x,y);
int lca=LCA(x,y);
split(lca),limit_access(x,dep[lca]);
if(y!=lca){
splay(lca);int son=v[v[lca].ch[1]].pre;
limit_access(y,dep[lca]),v[lca].extra=son,T::add(rd[son],cd[son],1);
}
}
int ask(int x,int y){
int lca=LCA(x,y);
return T::ask(rd[x])+T::ask(rd[y])-2*T::ask(rd[lca]);
}
}
void dfs1(int x,int prt){
fa[x]=prt,dep[x]=dep[prt]+1,sz[x]=1;
for(int y:vec[x])if(y!=prt)dfs1(y,x),sz[x]+=sz[y],son[x]=(sz[y]>sz[son[x]]?y:son[x]);
LCT::v[x].fa=prt;
}
void dfs2(int x,int prt,int top){
tp[x]=top,rd[x]=++sign;
if(son[x])dfs2(son[x],x,top);
for(int y:vec[x])if(y!=prt&&y!=son[x])dfs2(y,x,y);
cd[x]=sign;
}
int main() {
// system("fc edge.out edge5.ans");
freopen("edge.in","r",stdin);
freopen("edge.out","w",stdout);
int Ti=getint();
while(Ti--){
for(int i=1;i<=n;i++)vec[i].clear();
sign=0;
memset(fa,0,sizeof(fa));
memset(sz,0,sizeof(sz)),memset(son,0,sizeof(son));
LCT::init();
n=getint(),m=getint();
for(int i=1;i<n;i++){
int u=getint(),v=getint();
vec[u].push_back(v),vec[v].push_back(u);
}
dfs1(1,0),dfs2(1,0,1);
for(int i=1;i<=m;i++){
int opt=getint(),x=getint(),y=getint();
if(opt==1)LCT::expose(x,y);
if(opt==2)wrt(LCT::ask(x,y)),pc('\n');
}
}
fwrite(wb,1,p2,stdout);
return Loli Kon;
}
- 虽然做法迥异，但对于每个人来说考场上还是擅长啥写啥，不要尝试剑走偏锋。（