9/27(0.5h)+10/1(3h)
T2 看不懂，T3 调成狗。
T1，点数的尽可能少提示性强，往完全图方向想，写了个暴力找不同路径数，发现 \(i->n\) 决定二进制的该位。
T3，删除相邻的边，要求删除后最短路的最大值。显然删除的这条边只可能在最短路的路径上。考虑建最短路径树。对于 \(fa->x\) 这条边肯定要删去。那么删去之后我们肯定是以最短路径要走到 \(x\) 的子树外的，然后再走到 1 号点，但是 \(fa->x\) 被封了，所以我们并不知道最短路径如何走。但是考虑子树处理完了，假如 \(v,v\in tree_x\)，显然我们可以先让 \(x\) 走到 \(v\)，然后看看能不能通过 \(v\) 的边走到 \(z\)，\(z\) 在 \(x\) 的子树外，接下来 \(dis_z\) 就是 \(z->1\) 的路径长度了。
那么答案贡献式就是 \((dis_v-dis_x)+(v->z)+dis_z\)。但是注意，有可能删去之后还不如不删，所以最后再与最开始最短路取个 max。
我们可以考虑维护子树内的点集，这个可以用 vector+启发式合并，然后要维护点是否在子树内，可以用 map+启发式合并，接下来维护 \((dis_v-dis_x)+(v->z)+dis_z\) 的最小值。拆下，发现就是维护 \(dis_v+(v->z)+dis_z\) 的最小值。用个 set+启发式合并维护下，即每次都去找与当前点相邻的点，然后插入。考虑在贡献答案时顺便删去 \(v\) 在当前子树内的无用贡献，因为现在在子树内，到了祖先肯定也会在子树内。
这样子是 \(O(n\log^2 n)\) 的。
补充张图
T1
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define int ll
using namespace std;
int rd() {
char ch=getchar(); int f=1,sum=0;
while(ch<'0'||ch>'9') {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0') sum=sum*10+ch-'0',ch=getchar();
return sum*f;
}
ll lrd() {
char ch=getchar(); ll f=1,sum=0;
while(ch<'0'||ch>'9') {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0') sum=sum*10+ch-'0',ch=getchar();
return sum*f;
}
vector >ans;
signed main() {
freopen("review.in","r",stdin); freopen("review.out","w",stdout);
ll n=lrd(); int m=log2(n)+1;
for(int i=1;i<=m+1;i++) {
for(int j=i+1;j<=m+1;j++) ans.push_back(make_pair(i,j));
}
int nw=(1ll<<(m-1)),x=m+1;
while(nw) {
if(n>=nw) {
n-=nw; ans.push_back(make_pair(x,m+2));
}
nw>>=1; --x;
}
printf("%lld %lld\n",m+2,ans.size());
for(int i=0;i
T3
#include
#include
#include
#include
#include
#include
#include
#include
#include