题解：P15247 [WC2026] 画树
SegTree
·
·
题解
本文参考了这篇题解。
求出 k_{\min}
注意到每个点的度数和这个点上停留的橡皮和铅笔个数和的奇偶性不变。因此，对于变化的每个点最终状态都有一个铅笔或者橡皮。因此，答案的下界是 T_1 与 T_2 度数不同的点个数 /2。特别地，若 T_1\ne T_2 答案需要对 1 取 \max。
我们将通过给出构造说明这一点。
一些基本操作
$\text{alter}(x,z,y)$，其中 $y,z$ 表示原来铅笔和橡皮所在的位置，即可实现交换一对铅笔和橡皮的位置。
### 将 $T_2$ 转化为度数奇偶性与 $T_1$ 相同
在每个变化的点上放一个铅笔或橡皮。那目标即为将同一对铅笔和橡皮移动到同一个位置。
考虑若橡皮不是叶子，那找一个不含铅笔的儿子 $z$ 然后 $\text{alter}(t,z,z)$ 即可。由于可以交换铅笔和橡皮，铅笔不是叶子也能够解决。
对于铅笔和橡皮都是叶子的情况，可以让橡皮移动到它的唯一出边，然后把铅笔移到橡皮所在的位置。则当 $T_2$ 非链时可以转化为上种情况。为了规避链的情况，可以规定一对铅笔和橡皮尽量划给奇偶性不同的两个点。
### 将 $T_1$ 和 $T_2$ 转化中间状态
考虑最小化非 $1$ 节点的度数，不难发现每个点度数都可以被降到 $2$ 以下。具体地，若 $u$ 有儿子 $x,y$，则执行操作 $\text{alter}(x,x),\text{alter}(1,u),\text{alter}(y,y)$。
此时树的形态形如一个根挂若干条链。我们可以用如下操作合并两条链，记第一条链的链尾为 $x-y$，第二条链的链头为 $u$，执行操作 $\text{alter}(u,u),\text{alter}(x,1),\text{alter}(1,x),\text{alter}(y,y)$。操作后第二条链被并到 $x$ 之后，而 $y$ 被孤立为 $1$ 的一个儿子。
此时树的形态形如一个根挂一条链和若干叶子。我们容易通过操作使得链尾的编号最小。
此时我们希望对中间那条链进行排序。发现对 $T[l,r]$ 做区间翻转是容易的，只需进行操作：
$rev(l,r):\text{alter}(T_{l-1},T_{l-1}),\text{alter}(T_r,T_l),\text{alter}(T_l,T_r),\text{alter}(T_{r+1},T_{r+1})$。
对于 $\text{swap}(T_l,T_r)$ 只需 $rev(l,r),rev(l+1,r-1)$ 即可。
这样链变得有序，哪些挂的是叶子也是确定的。因此一个度数奇偶性状态唯一对应这样一个中间状态。
### 操作次数分析
精细实现可以做到 $O(n)$。由于限制较为宽松且树随机生成，实现成 $O(n^2)$ 也可以通过。
### 代码
:::info[Code]
```cpp line-numbers
#include<bits/stdc++.h>
// #include"paint.h"
void setting(int k, std::vector<int> p);
void alter(int t, int x, int y);
#define up(i,l,r) for(int i=(l);i<=(r);++i)
#define down(i,l,r) for(int i=(l);i>=(r);--i)
#define pi pair<int,int>
#define p1 first
#define p2 second
#define m_p make_pair
#define pb push_back
#define eb emplace_back
using namespace std;
void init(int c,int t){}
int d1[505],d2[505],id1[505],id2[505];
void paint(int n,vector<int>u,vector<int>v){
vector<pi>e1,e2;
up(i,0,n-2)e1.eb(min(u[i],v[i]),max(u[i],v[i]));
up(i,n-1,2*n-3)e2.eb(min(u[i],v[i]),max(u[i],v[i]));
sort(e1.begin(),e1.end()),sort(e2.begin(),e2.end());
if(e1==e2)return setting(0,{});
up(i,1,n)d1[i]=d2[i]=0;
for(auto [x,y]:e1)d1[x]++,d1[y]++;for(auto [x,y]:e2)d2[x]++,d2[y]++;
int k=0;up(i,1,n)k+=(d1[i]^d2[i])&1;k=max(k/2,1);
vector<int>p(k,1);setting(k,p);
vector<tuple<int,int,int> >ans[3];
auto work1=[&](){
multiset<int>s[505];
for(auto [x,y]:e2)s[x].insert(y),s[y].insert(x);
auto del=[&](int x,int y){s[x].erase(s[x].find(y)),s[y].erase(s[y].find(x));};
auto ins=[&](int x,int y){s[x].insert(y),s[y].insert(x);};
auto op=[&](int x,int y,int z){ans[2].eb(x,id2[x],id1[x]);ins(id1[x],y),del(id2[x],z);id1[x]=y,id2[x]=z;};
vector<int>nd[2];
up(i,1,n)if((d1[i]^d2[i])&1)nd[d2[i]&1].eb(i);
int tot=0;
while(nd[0].size()||nd[1].size()){
int u=0,v=0;
if(nd[0].size()&&nd[1].size())
u=nd[0].back(),v=nd[1].back(),nd[0].pop_back(),nd[1].pop_back();
else if(nd[0].size())
u=nd[0].back(),nd[0].pop_back(),v=nd[0].back(),nd[0].pop_back();
else
u=nd[1].back(),nd[1].pop_back(),v=nd[1].back(),nd[1].pop_back();
++tot;id1[tot]=u,id2[tot]=v;
}
if(tot){
function<bool(int,int,int)> in=[&](int u,int x,int fa){
if(u==x)return 1;
for(int p:s[u])if(p!=fa&&in(p,x,u))return 1;
return 0;
};
up(i,1,tot){
while(id1[i]!=id2[i]){
if(s[id1[i]].size()==1&&s[id2[i]].size()==1)op(i,id2[i],(*s[id2[i]].begin()));
else{
if(s[id2[i]].size()==1)op(i,id2[i],id1[i]);
int pos=-1;
for(int p:s[id2[i]])if(!in(p,id1[i],id2[i])){pos=p;break;}
op(i,pos,pos);
}
}
if(id1[i]!=1)op(i,1,1);
}
}
e2.clear();
up(i,1,n)for(int x:s[i])if(i<x)e2.eb(i,x);
};work1();
auto work2=[&](int o,vector<pi>e){
up(i,1,k)id1[i]=id2[i]=1;
multiset<int>s[505];
vector<int>to1(505,0),to2(505,0);
for(auto [x,y]:e)s[x].insert(y),s[y].insert(x);
auto del=[&](int x,int y){s[x].erase(s[x].find(y)),s[y].erase(s[y].find(x));};
auto ins=[&](int x,int y){s[x].insert(y),s[y].insert(x);};
auto op=[&](int x,int y,int z){if(o)ans[1].eb(x,id2[x],id1[x]);ins(id1[x],y),del(id2[x],z);id1[x]=y,id2[x]=z;if(!o)ans[o].eb(x,y,z);};
auto it=s[1];
function<void(int,int)>dfs=[&](int u,int fa){
for(int x:s[u])if(x!=fa)dfs(x,u);
while(s[u].size()>2){
int x=0,y=0;
auto it=s[u].begin();x=*it;y=*(++it);
if(x==fa)x=*(++it);else if(y==fa)y=*(++it);
op(1,x,x),op(1,1,u),op(1,y,y);
}
};
for(int x:it)dfs(x,1);
vector<int>vec;
for(int x:s[1])if(s[x].size()!=1)vec.eb(x);
auto get=[&](int p){
int t=p;
int la=1;
while(s[p].size()==2){
int to=-1;
for(int x:s[p])if(x!=la)to=x;
la=p,p=to;
}
to1[t]=p,to2[t]=la;
};
for(int x:vec)get(x);
up(i,1,(int)vec.size()-1){
op(1,vec[i],vec[i]);
op(1,to2[vec[0]],1);
op(1,1,to2[vec[0]]);
op(1,to1[vec[0]],to1[vec[0]]);
to1[vec[0]]=to1[vec[i]];
to2[vec[0]]=to2[vec[i]];
}
if(vec.size()){
int mn=1e9;
for(int x:s[1])if(x!=vec[0])mn=min(mn,x);
if(mn<to1[vec[0]]){
op(1,mn,mn);
op(1,to2[vec[0]],1);
op(1,1,to2[vec[0]]);
op(1,to1[vec[0]],to1[vec[0]]);
}
vector<int>C={1};
int u=vec[0],la=1;
while(s[u].size()==2){
C.eb(u);int to=-1;
for(int x:s[u])if(x!=la)to=x;
la=u,u=to;
}C.eb(u);
vector<int>D(C.size(),0);
up(i,1,(int)C.size()-2)up(j,1,(int)C.size()-2)D[i]+=C[j]<=C[i];
auto rev=[&](int l,int r){
if(l>=r)return;
op(1,C[l-1],C[l-1]);
op(1,C[r],C[l]);
op(1,C[l],C[r]);
op(1,C[r+1],C[r+1]);
reverse(C.begin()+l,C.begin()+r+1);
reverse(D.begin()+l,D.begin()+r+1);
};
auto upd=[&](int x,int y){
if(x>y)swap(x,y);
rev(x,y),rev(x+1,y-1);
};
up(i,1,(int)C.size()-2)if(D[i]!=i){
int pos=-1;
up(j,1,(int)C.size()-2)if(D[j]==i)pos=j;
upd(i,pos);
}
}
if(id1[1]!=1)op(1,1,1);
// up(i,1,n)for(int x:s[i])if(i<x)cerr<<i<<" "<<x<<endl;cerr<<endl;
};
work2(0,e1),work2(1,e2);
auto rev=[&](int o){reverse(ans[o].begin(),ans[o].end());};rev(1),rev(2);
up(i,0,2)for(auto [t,x,y]:ans[i])alter(t,x,y);
}
```