题目描述
作为一个熟练的 OI 选手，你对数据结构的各种题型早已轻车熟路，比赛中只要碰到数据结构题就能三下五除二轻松搞定。这一天，你翻开 OJ，看到了这道题：
给定 \(n\) 个点的有根树，点编号为 \(1, 2, \dots, n\)，\(1\) 为根。每条边上有一个 \(1\) 至 \(n - 1\) 的两两不同的权值。维护一个数据结构，支持交换权值为 \(x\) 和 \(y\) 的边的权值，以及询问从根节点到 \(u\) 号点的所有的边的权值最大值。
这种简单而经典的树上问题，对你已经是不在话下。厌倦了维护修改，回答询问的你，打算换一个角色。这回，你才是那个提问题的人，你需要构造合适的操作来套取题的数据。
具体地说，现在你并不知道树的结构，也不知道初始时树上每条边的权值，你需要通过如下两种操作得到树的结构和 初始时 树上每条边的权值：
- 给出正整数 \(x, y\)，其中 \(1 \le x, y < n\)，\(x \neq y\)，交换 权值为 \(x, y\) 的两条边的权值。
- 给出正整数 \(u\)，其中 \(2 \le u \le n\)，并得到从 \(1\) 号点到 \(u\) 号点的路径上所有边中权值的最大值。
题目保证树的形态和每条边的权值是预先给定的，不会根据你的操作而动态生成。
子任务
| 子任务编号 | \(n \leq\) | 特殊性质 | \(lim1=\) | \(lim2=\) | 分值 |
|---|---|---|---|---|---|
| \(1\) | \(\leq 50\) | A | \(1\,000\,001\) | $1,000,001 $ | \(6\) |
| \(2\) | \(\leq 1\,000\) | 无 | \(1\,100\,002\) | \(2\,200\,002\) | \(9\) |
| \(3\) | \(\leq 10^5\) | A | \(3\,000\,003\) | \(3\,000\,003\) | \(14\) |
| \(4\) | \(\leq 20\,000\) | B | \(3\,000\,004\) | \(3\,000\,004\) | \(14\) |
| \(5\) | \(\leq 10^5\) | 无 | \(3\,000\,005\) | \(3\,000\,005\) | \(21\) |
| \(6\) | \(\leq 5 \cdot 10^5\) | A | \(3\,500\,006\) | \(3\,500\,006\) | \(11\) |
| \(7\) | 无 | 无 | \(3\,500\,007\) | \(3\,500\,007\) | \(25\) |
特殊性质 A：
- 每个节点有不超过 \(1\) 个儿子，即树的形态是一条链；
- 链的非根节点标号在所有可能的标号中等概率随机；
- 边的权值排列在所有 \((n - 1)!\) 种可能的排列中等概率随机。
特殊性质 B：
- 树形态按如下方式随机生成：
- 先对每个 \(2 \le i \le n\)，令 \(i\) 的父亲在 \([1, i - 1]\) 的整数之间等概率随机选取，
- 再等概率随机打乱非根节点的编号，得到最终的带标号有根树的结构。
- 边的权值排列在所有 \((n - 1)!\) 种可能的排列中等概率随机。
你可以根据 \(lim1, lim2\) 的值来判断数据所满足的特殊性质。
题解
记\(Q(x)\)表示询问\(x\)到根的路径上的最大值的结果。
默认\(Q(1)=0\)。
算法1
我会\(O(n^2)\)！
对于一棵树，考虑对每个边权\(i\)，我们先将\(i\)换成\(n-1\)，然后对于点\(2\)至点\(n\)执行\(query\)操作，这样我们可以根据\(Q(x)\)是否为\(n-1\)得出初始时，边权为\(x\)的边下面的子树有哪些节点，然后再将\(i\)换回去。
记边权为\(x\)的边下面的子树的节点构成的点集为\(S_i\)。
考虑如何通过这些信息还原出树。
对于一个点\(x\)，我们枚举\(i\)，找所有的\(x\in S_i\)中\(|S_i|\)的最小值\(minn\)与严格次小值\(second\_min\)，同时记录最小值对应的边权\(min\_id\)与严格次小值对应的边权\(second\_min\_id\)。
最小值对应的边权即为\(i\)连向\(fa_i\)的边权。
若次小值不存在，则该点父亲为根，也就是\(1\)号点。
否则，考虑记\(rnk[x]\)表示\(i\)连向\(fa_i\)的边权为\(x\)的\(i\)，可通过\(rnk\)数组还原出\(fa_i\)，具体地说，\(fa_i=rnk[second\_min\_id[i]]\)。
可以通过子任务\(1,2\)，获得\(15\)分。
代码
#include<bits/stdc++.h>
#include "ds.h"
#define For(i,l,r) for(int i=(l);i<=(r);++i)
const int N=1010;
const int inf=1e9;
using namespace std;
bool subtree[N][N];
int minn[N],second_min[N],min_id[N],second_min_id[N],siz_e[N],fa[N],fa_val[N],rnk[N];
vector<int> par,val;
void solve(int n,int lim1,int lim2)
{
{
For(edge_val,1,(n-1))
{
For(i,2,n)
subtree[edge_val][i]=false;
}
For(i,2,n)
minn[i]=inf;
For(i,2,n)
second_min[i]=(inf-1);
For(i,1,(n-1))
siz_e[i]=0;
};
For(edge_val,1,(n-2))
{
exchange(edge_val,(n-1));
For(i,2,n)
{
if(query(i)==(n-1))
subtree[edge_val][i]=true;
else
subtree[edge_val][i]=false;
}
exchange(edge_val,(n-1));
}
{
For(i,2,n)
{
if(query(i)==(n-1))
subtree[n-1][i]=true;
else
subtree[n-1][i]=false;
}
};
For(edge_val,1,(n-1))
{
For(j,2,n)
{
if(subtree[edge_val][j]==true)
++siz_e[edge_val];
}
}
{
For(j,2,n)
{
For(edge_val,1,(n-1))
{
if(subtree[edge_val][j]==false)
continue;
if(minn[j]==inf && second_min[j]==(inf-1))
{
minn[j]=siz_e[edge_val];
min_id[j]=edge_val;
continue;
}
if(minn[j]!=inf && second_min[j]==(inf-1))
{
if(minn[j]<siz_e[edge_val])
{
second_min[j]=siz_e[edge_val];
second_min_id[j]=edge_val;
continue;
}
else if(siz_e[edge_val]<minn[j])
{
second_min[j]=minn[j];
second_min_id[j]=min_id[j];
minn[j]=siz_e[edge_val];
min_id[j]=edge_val;
continue;
}
}
if(minn[j]!=inf && second_min[j]!=(inf-1))
{
if(minn[j]<siz_e[edge_val] && siz_e[edge_val]<second_min[j])
{
second_min[j]=siz_e[edge_val];
second_min_id[j]=edge_val;
continue;
}
else if(siz_e[edge_val]<minn[j])
{
second_min[j]=minn[j];
second_min_id[j]=min_id[j];
minn[j]=siz_e[edge_val];
min_id[j]=edge_val;
continue;
}
}
}
}
};
{
For(i,2,n)
fa_val[i]=min_id[i];
For(i,2,n)
rnk[fa_val[i]]=i;
For(i,2,n)
{
if(second_min[i]==(inf-1))
fa[i]=1;
else
fa[i]=rnk[second_min_id[i]];
}
};
{
par.clear();
For(i,2,n)
par.push_back(fa[i]);
val.clear();
For(i,2,n)
val.push_back(fa_val[i]);
};
answer(par,val);
return;
}
首先我们注意到操作可逆，因此只要把操作记录下来，并且知道最后的边权分布，就可以还原出初始的边权分布。
其次我们可以假设点编号和边权都是随机生成的，否则可以随机打乱点的编号，再用若干次操作随机排列边权。
之后的算法默认会进行记录操作与随机打乱点编号，边权。
算法2
考虑特殊性质\(A\)，想必大家都会\(O(n^2)\)，这里就不再说了，各显神通。
如果对于\(i\in[1,n]\)，我们都能维护出\(1,2,...,i\)号点在链上的顺序，且相邻两个点之间的边权是连续的，而且这些边权连续段中的\(max\)从左到右是递增的，那么做到\(n\)时，整条链的形态就是第\(1\)个点后面连着边权为\(1\)的边，第\(2\)个点后面连着边权为\(2\)的边，...，由此我们可以还原出原来的链。
举个例子，假设\(n=7\)，我们已经维护出\(1,2,3\)在链上的顺序为\(1,3,2\)，\(1\)到\(3\)之间边权为\(1\)到\(3\)的排列，\(3\)到\(2\)之间边权为\(4\)到\(5\)的排列，现在要插入\(4\)，若\(Q(4)=6\)，则\(4\)的位置在\(2\)右侧，若\(Q(4)=2\)，则\(4\)的位置在\(1,3\)之间，也即\(1\)的右侧，\(3\)的左侧。
考虑如何在从\(i\)变为\(i+1\)后维护出这些信息。
我们需要先询问一次\(Q(i+1)\)，然后我们再询问\(Q(1),Q(2),Q(3),...,Q(i)\)中最大的\(<=Q(i+1)\)的数，记为\(x\)，然后我们交换\(\{x+1,Q(i+1)\}\)，\(\{x+2,Q(i+1)\}\)，直到\(i+1\)到左边第一个编号\(<=i\)之间的边的边权在值域上是一个连续段。
注意\(Q(i+1)\)是动态变化的，也就是说我们在每次交换操作之后都需要重新询问\(Q(i+1)\)。
由于我们需要询问\(Q(1),Q(2),Q(3),...,Q(i)\)中最大的\(<=Q(i+1)\)的数，所以我们可以使用一个\(set\)来维护，每次查找时\(lower\_bound\)即可。
由于点编号与边权都是随机生成的，而在期望意义下相邻两个点的边数是\(O(\frac{n}{i})\)，因此第\(i\)次插入的期望代价是\(O(\frac{n}{i})\)，所以总代价约为\(n\ ln\ n\)，复杂度为\(O(n\ log\ n)\)。
可以通过子任务\(1,3\)，结合算法1，可以获得\(29\)分。
代码
#include<bits/stdc++.h>
#include "ds.h"
#define For(i,l,r) for(int i=(l);i<=(r);++i)
#define ReFor(i,r,l) for(int i=(r);i>=(l);--i)
const int N=100010;
const int M=3500010;
using namespace std;
int cnt;
int fa[N],fa_val[N],p[N],nxt[N],pos[N],inv_pos[N];
vector<int> par,val;
set<int> Q;
struct node{int x,y;}a[M];
void exchange1(int x,int y)
{
if(x==y)
return;
else
{
++cnt;
a[cnt].x=x;
a[cnt].y=y;
exchange(x,y);
}
return;
}
mt19937 rnd(time(0));
void solve(int n,int lim1,int lim2)
{
{
cnt=0;
Q.insert(0);
For(i,2,n)
p[i]=i;
shuffle(p+2,p+n+1,rnd);
For(edge_val,2,(n-1))
{
int _=(((rnd())%(edge_val-1))+1);
exchange1(_,edge_val);
}
};
For(_,2,n)
{
int i=p[_];
int Q_i=query(i);
int x=*(--Q.lower_bound(Q_i));
for(int edge_val=(x+1);edge_val;++edge_val)
{
if(Q_i<=edge_val)
break;
exchange1(edge_val,Q_i);
Q_i=query(i);
}
Q.insert(Q_i);
}
{
For(_,2,n)
{
int i=p[_];
int Q_i=query(i);
nxt[Q_i]=i;
}
};
{
nxt[0]=1;
For(i,1,(n-1))
fa[nxt[i]]=nxt[i-1];
For(i,1,(n-1))
pos[i]=i;
ReFor(i,cnt,1)
swap(pos[a[i].x],pos[a[i].y]);
For(i,1,(n-1))
inv_pos[pos[i]]=i;
For(i,1,(n-1))
fa_val[nxt[i]]=inv_pos[i];
};
{
par.clear();
For(i,2,n)
par.push_back(fa[i]);
val.clear();
For(i,2,n)
val.push_back(fa_val[i]);
};
answer(par,val);
return;
}
算法3
注意到算法2很有前途！
仍然考虑特殊性质\(A\)，沿用算法2的想法，但我们在维护\(1,2,..,x\)在链上的顺序时，我们忽略边权\(<n-x\)的边，只关注边权\(>=n-x\)的边，那么我们只需满足相邻点之间\(>=n-x\)的边的边权在值域上构成连续段且这些边权连续段的\(max\)从左到右递增即可。
但是事实上，在这里，相邻的两个点直接可能没有边，因为我们的边数跟点数相同，所以可能会出现两个点之间有着若干条边的情况，但这并没有关系，我们可以把点分成若干段，这样一来，我们只需要维护每个段内有哪些点，还有段与段之间在链上的顺序即可，段内点是任意排列的。
考虑如何在\(x\)变为\(y(x<y)\)后仍然维护出这些信息，我们需要插入点\(x+1\)至点\(y\)，使用算法2的方法，可以得知每个点需要插在哪个段内，将点插入后与算法2同理维护顺序关系即可。
但是我们需要考虑边权在\([n-y,n-x-1]\)区间内的边了。
仍然使用算法2的方法，将边插入，插入后维护顺序关系，我们需要让相邻两段之间所有边权\(>=n-y\)的边的边权构成连续段，且从左到右\(max\)递增，类似算法2，开一个集合存\(Q\)的值，插入时在其中二分出小于等于的最大值，然后交换直至满足条件为止。
而且我们需要从左往右插，可能说的比较抽象，举个例子好了。
例如有一条\(n=4\)的链。
最开始，我们有一个点\(1\)，一条边\(3\)。
然后，我们插入\(2\)，假设\(Q(2)=3\)，那么我们现在把点分成了两段，第一段内只有一个\(1\)，第二段内只有一个\(2\)，我们知道两段之间有一条边\(3\)。
接下来我们考虑边权为\(2\)的边，将其插入后，使用算法\(2\)的方法，交换至满足要求。。
假设交换后\(Q(2)=2\)。
接下来，我们插入\(3,4\)，假设\(Q(3)=3,Q(4)=2\)，那么我们现在把点分成了三段，第一段内只有一个\(1\)，第二段内有\(2,4\)，\(2,4\)的相对顺序我们不知道，第三段内只有一个\(3\)，第一段与第二段间有一条边\(2\)，第二段与第三段间有一条边\(3\)。
将边权为\(1\)的边插入，执行交换操作，将从左到右的边的边权换为\(1,2,3\)，询问\(Q(2)\)和\(Q(4)\)即可定出它们的相对顺序，若\(Q(2)=1,Q(4)=2\)，则链形态为\(1,2,4,3\)，若\(Q(2)=2,Q(4)=1\)，则链的形态为\(1,4,2,3\)。
段内的点数个数更多的情况也是类似的，根据\(Q\)值排序即可。
我们实际上就是先对段排序，然后对于每个段在段内根据\(Q\)值排序，即可得到链的形态。
如果还是不明白，详见代码中\(solve\_chain\)和\(work2\)部分。
注意到在每个时刻，点和边总是同级别的，因此一次插入的期望代价是\(O(1)\)，所以复杂度是\(O(n)\)的，实现的时候我们可以倍增，从\(x\)变为\(2x\)或\(3x\)，实测\(3x\)略优于\(2x\)，而且本题略微卡常，所以建议从\(x\)变为\(3x\)。（因为不卡一下的话\(nlogn\)就过了。）
可以通过子任务\(1,3,6\)，结合算法1，可以获得\(40\)分。
需要实现线性找出链尾，剩余部分被算法4的实现完全包含，故不单独给出实现，可以参考算法4的代码部分。
算法4
注意到一棵树可以表示为若干条链的并。
那么一个大概的想法就是我们先将树拆分为若干条互不相交的链（点不交），然后对每条链跑链的做法，最后再以某种方式将这些链拼起来，形成原树。
拆链的时候，对每条链我们需要记录：这条链上有哪些点，这条链的链顶是谁，这条链的链尾是谁。对每条链跑完链的做法之后，我们可以知道这条链上的点的顺序，以及链顶的点到其父亲的边的边权，而且我们可以使每条链上的边（包括链顶的点指向父亲的那条边。）的边权在值域上构成连续段，且其从顶到底，边权递增，换句话说就是满足小根堆的性质。
如何将链拼起来？
记\(size_i\)表示以\(i\)为结尾的链上有多少个点，不妨将第\(i\)条链上的权值分配为\([(\sum\limits_{j=1}^{i-1}size_j)+1,\sum\limits_{j=1}^{i}size_j]\)。
对于边权为\(1\)的边所在的那条链，我们将\(1\)换至链底，然后其他边权保持相对顺序不变，即链上的边权从顶到底由\(1,2,3,...\)变为\(2,3,...,1\)，这是简单的，我们只需要依次执行\(exchange(1,2),...\)即可。
我们现在相当于在维护一个链并，链并满足小根堆性质，新增一条链，记新增的链的链顶为\(x\)，\(x\)连向\(x\)父亲的边的边权为\(val\)，交换\(1,val\)之后，我们只需要询问\(Q(x)\)即可得知\(x\)的父亲，然后将\(1,val\)换回来。
为什么？由于执行交换操作后，剩余的边仍然满足小根堆性质，那么我们询问\(Q(x)\)后，若返回值为\(1\)，则说明\(x\)直接连在根下面，否则，返回的是原树上\(x\)的父亲\(y\)到\(y\)的父亲的边的权值。
当然，为了保持小根堆性质，我们将这条链接上去之后还要做一些交换操作以保持性质。
上面说的比较简略，只是一个大概的想法，具体地说，我们在实现时需要做这样几件事情。
首先需要拆链，其实这一步只要保证每一个点都恰好在一条链内，且每条链上的权值在值域上是连续段，就可以保证复杂度是对的，拆链时记录链顶，链尾，链上有哪些点，记得复杂度要是线性的。
其次，我们对于每条链跑链的做法，做出每条链内的点的相对顺序，以及将边权按从链顶到链尾的顺序递增排列好。
最后，我们维护一个链并，每次将一条链加入，加入时按上述方法操作，交换的话，假设我们维护了一个根到\(2\)号点，\(3\)号点，...，\(i\)号点的链的链并，记这个链并为\(S_i\)，那么我们加入的这条链可以记为\(S_{i+1}-S_i\)，对于加入的这条链上的每个点，我们按从顶到底的顺序（包括\(x\)指向其父亲的边。）将边权依次交换为\(|S_i|+2,|S_i|+3,...,|S_{i+1}|+1\)即可。
如果对实现有疑问可以看代码。
拆链部分是线性的，拼链部分是线性的，复杂度取决于使用的链的做法的复杂度，若是\(O(n\ log\ n)\)的，则复杂度为\(O(n\ log\ n)\)，可以通过子任务\(1,2,3,4,5\)，获得\(64\)分，若是\(O(n)\)的，则复杂度为\(O(n)\)，若常数较大，则只可以通过子任务\(1,2,3,4,5\)，获得\(64\)分，略微精细实现一下即可通过子任务\(1,2,3,4,5,6,7\)。（我一开始的实现在倍增时每次\(*2\)，喜提\(64\)分，改成每次\(*3\)之后过了。）
代码
#include<bits/stdc++.h>
#include "ds.h"
#define For(i,l,r) for(int i=(l);i<=(r);++i)
#define ReFor(i,r,l) for(int i=(r);i>=(l);--i)
const int N=500010;
const int M=3500010;
using namespace std;
int cnt;
int fa[N],fa_val[N],p[N],pos[N],inv_pos[N],num[N],inv_fa_val[N];
vector<int> par,val;
struct node{int x,y;}a[M];
mt19937 rnd(time(0));
void exchange1(int x,int y)
{
if(x==y)
return;
else
{
++cnt;
a[cnt].x=x;
a[cnt].y=y;
exchange(x,y);
}
return;
}
void exchange2(int x,int y)
{
if(x==y)
return;
else
{
++cnt;
a[cnt].x=x;
a[cnt].y=y;
int inv_fa_val_x=inv_fa_val[x],inv_fa_val_y=inv_fa_val[y];
inv_fa_val[x]=inv_fa_val_y;
inv_fa_val[y]=inv_fa_val_x;
fa_val[inv_fa_val_x]=y;
fa_val[inv_fa_val_y]=x;
exchange(x,y);
}
return;
}
int work1(int x,int edge_val)
{
for(int i=(edge_val+1);i;++i)
{
int Q_x=query(x);
if(Q_x<=i)
return Q_x;
exchange1(Q_x,i);
}
}
set<int> S;
int work2(int x)
{
int Q_x=query(x);
auto it=S.lower_bound(Q_x);
if(it!=S.begin())
--it;
int star_t=*it;
for(int i=(star_t+1);i;++i)
{
if(Q_x<=i)
return Q_x;
exchange1(Q_x,i);
Q_x=query(x);
}
}
vector<int> chain[N];
void solve_chain(int l,int r)
{
shuffle(chain[r].begin(),chain[r].end(),rnd);
vector<int> rebuild;
for(int i=(r-l);i;i/=3)
rebuild.push_back(i);
reverse(rebuild.begin(),rebuild.end());
for(auto i:rebuild)
{
S.clear();
S.insert(r-i);
For(j,0,(i-1))
{
num[chain[r][j]]=work2(chain[r][j]);
S.insert(num[chain[r][j]]);
}
{
auto cmp=[&](int x,int y)->bool{return num[x]<num[y];};
sort(chain[r].begin(),chain[r].begin()+i,cmp);
};
}
return;
}
void solve(int n,int lim1,int lim2)
{
{
cnt=0;
For(i,2,n)
p[i]=i;
shuffle(p+2,p+n+1,rnd);
For(edge_val,2,(n-1))
{
int _=(((rnd())%(edge_val-1))+1);
exchange1(_,edge_val);
}
};
{
int last_max=0;
set<int> s;
s.clear();
For(_,2,n)
{
int i=p[_];
int maxx=work1(i,last_max);
auto it=s.lower_bound(maxx);
if(it==s.end())
{
s.insert(maxx);
chain[maxx].push_back(i);
last_max=maxx;
}
else
chain[*it].push_back(i);
}
};
{
int las_t=0;
For(i,1,n)
{
if(chain[i].empty())
continue;
solve_chain(las_t,i);
las_t=i;
}
};
{
int edge_val=0,id=-1,end_val=-1;
For(i,1,n)
{
if(chain[i].empty())
continue;
int len=chain[i].size();
For(j,0,(len-1))
{
++edge_val;
if(edge_val==1)
id=i;
fa_val[chain[i][j]]=edge_val;
inv_fa_val[edge_val]=chain[i][j];
}
For(j,1,(len-1))
fa[chain[i][j]]=chain[i][j-1];
}
for(auto _:chain[id])
end_val=max(end_val,fa_val[_]);
For(_,2,end_val)
exchange2(1,_);
};
{
int S_=0;
For(i,1,n)
{
if(chain[i].empty())
continue;
int Fa_val=fa_val[chain[i][0]];
exchange2(1,fa_val[chain[i][0]]);
int maxx=query(chain[i][0]);
if(maxx==1)
fa[chain[i][0]]=1;
else
fa[chain[i][0]]=inv_fa_val[maxx];
exchange2(1,fa_val[chain[i][0]]);
for(auto _:chain[i])
{
++S_;
if((S_+1)<=(n-1))
exchange2(fa_val[_],(S_+1));
}
}
};
{
For(i,2,n)
par.push_back(fa[i]);
For(i,1,(n-1))
pos[i]=i;
ReFor(i,cnt,1)
swap(pos[a[i].x],pos[a[i].y]);
For(i,1,(n-1))
inv_pos[pos[i]]=i;
For(i,2,n)
val.push_back(inv_pos[fa_val[i]]);
};
answer(par,val);
return;
}
其中
{
int last_max=0;
set<int> s;
s.clear();
For(_,2,n)
{
int i=p[_];
int maxx=work1(i,last_max);
auto it=s.lower_bound(maxx);
if(it==s.end())
{
s.insert(maxx);
chain[maxx].push_back(i);
last_max=maxx;
}
else
chain[*it].push_back(i);
}
};
这一部分是将原树拆分成若干条链，算法3中提到的线性找链尾只需在其上稍加改动，记录\(las\_t\)表示上一个新开了一条链的点的编号，若\((it==s.end())\)，则将\(las\_t\)更新为\(i\)，这样做到最后，\(las\_t\)的值就是链尾的编号。
标签：WC,chain,val,int,题解,边权,CTS2023,fa,edge From： https://www.cnblogs.com/llzer/p/17449972.html