题解

kcs007 超级无敌管理员 LV 6 SU ~ 2025-11-19 17:58:40

2024暑期CSP-S&NOIP模拟赛第1套题解

T1 弹钢琴（piano）

30-70%

如果音 $a_i$ 能弹对，则说明 $a_i-a_1=b_ik$ 。其中 $b_i=\left\{\begin{matrix} b_{i-1}+1 & a_i>a_{i-1} \\ b_{i-1} & a_i=a_{i-1} \\ b_{i-1}-1 & a_i<a_{i-1} \end{matrix}\right.$ 且 $b_1=0$ 。

枚举与 $a_1$ 匹配的 $a_i$ ，算出对应的 $k$ ，然后对于剩余的去check算出的 $k$ 是否符合要求取 $max$ 即可，时间复杂度 $O(n^2)$

100%

观察 $a_i-a_1=b_ik$ ，发现已知 $i$ 时 $k$ 是唯一确定的，那么其实可以从每个 $k$ 考虑对答案的贡献即可避免之前做法的check，记 $c_k$ 表示确定 $k$ 后能弹对多少个音。初始 $c_i$ 均为 $1$ （ $a_1$ 均能弹对）。

由 $2$ 到 $n$ 递推。如果音 $a_i$ 弹对了，那么：

若 $b_i=a_i-a_1=0$ ，所有 $c_k$ 均加一。
若 $b_i$ 与 $a_i-a_1$ 异号或 $b_i=0$ 且 $a_i\neq a_1$ ，那么对 $c_k$ 无贡献。
若 $(a_i-a_1)\bmod b_i\neq0$ ，也对 $c_k$ 无贡献。
否则，记 $p=\dfrac{a_i-a_1}{b_i}$ ， $c_p$ 加一，即 $k=p$ 时的贡献加一。

递推过程中更新并记录即可。

时间复杂度 $O(n)$ 。

#include<bits/stdc++.h>
#include<unordered_map>
#define int long long
using namespace std;
const int N=1e6+10;
int a[N],b[N];
int n,tag,ans, pos;
unordered_map<int,int> num;
signed main(){
    freopen("piano.in", "r", stdin);
    freopen("piano.out", "w", stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=2;i<=n;i++){
        if(a[i]>a[i-1])
            b[i]=b[i-1]+1;
        else if(a[i]==a[i-1])
            b[i]=b[i-1];
        else b[i]=b[i-1]-1;
        int r=a[i]-a[1], q=b[i];
        int npos;
        if(q==0){
            if(r==0) ++tag,npos=pos;
            else continue;
        }
        else if(r==0) ++num[0],npos=0;
        else if(r<0&&q<0){
            r=-r;q=-q;
            if(r%q==0) ++num[r/q],npos=r/q;
        }
        else if((r<0&&q>0)||(r>0&&q<0))
            continue;
        else if(r%q==0) ++num[r/q],npos=r/q;
        if(ans==num[npos]+tag) pos=min(pos,npos);
        else if(ans<num[npos]+tag){
            ans=num[npos]+tag;
            pos=npos;
        }
    }
    cout<<ans+1<<'\n'<<pos;
    return 0;
}

考察知识点

桶，计数

T2 选彩笔（rgb）

可以从一维二纬的情况开始考虑

50%

发现RGB范围很小，可以考虑把RGB堪称三维空间，枚举一个长度（Colorfulness 值）再枚举答案组里RGB三个坐标的最大值，去这个空间里check是否存在k个点，时间复杂度约为 $O(R^7),R$ 为RGB的值域范围。

80%

枚举一个长度后发现check空间里是否存在k个点能通过三维前缀和+容斥维护得到，时间复杂度降为 $O(R^4),R$ 为RGB的值域范围。

100%

观察到题目要求差值最大值最小，注意到答案具有二分性，可以考虑二分长度。枚举 R,G,B 的最大值，计算在 R 值在区间 $[maxr-mid,maxr]$ 内，G 值在区间 $[maxg-mid,maxg]$ 内，B 值在区间 $[maxb-mid,maxb]$ 内的笔的个数。定义 $sum[i][j][k]$ R 值在区间 $[1,i]$ 内，G 值在区间 $[1,j]$ 内，B 值在区间 $[1,k]$ 内的笔的个数，可以通过三维前缀和求解。时间复杂度降为 $O(R^3 \log R),R$ 为RGB的值域范围。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100010][3],mx;
int sum[300][300][300];
int ct[3];
int rs(int x,int y,int z,int len){
    int rt=sum[x][y][z];
    rt-=(sum[x-len-1][y][z]+sum[x][y-len-1][z]+sum[x][y][z-len-1]);
    rt+=(sum[x-len-1][y-len-1][z]+sum[x-len-1][y][z-len-1]+sum[x][y-len-1][z-len-1]);
    rt-=sum[x-len-1][y-len-1][z-len-1];
    return rt;
}
bool check(int l){
    for(int i=l+1;i<=mx;i++){
        for(int j=l+1;j<=mx;j++){
            for(int k=l+1;k<=mx;k++){
                if(rs(i,j,k,l)>=m){
                    ct[0]=i;
                    ct[1]=j;
                    ct[2]=k;
                    return 1;
                }
            }
        }
    }
    return 0;
}
int main(){
    freopen("rgb.in", "r", stdin);
    freopen("rgb.out", "w", stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
        a[i][0]++;//为了避免边界情况讨论，整体增加一
        a[i][1]++;
        a[i][2]++;
        mx=max(mx,a[i][0]);
        mx=max(mx,a[i][1]);
        mx=max(mx,a[i][2]);
        sum[a[i][0]][a[i][1]][a[i][2]]++;
    }
    for(int i=1;i<=mx;i++)for(int j=1;j<=mx;j++)for(int k=1;k<=mx;k++)sum[i][j][k]+=sum[i][j][k-1];
    for(int i=1;i<=mx;i++)for(int k=1;k<=mx;k++)for(int j=1;j<=mx;j++)sum[i][j][k]+=sum[i][j-1][k];
    for(int i=1;i<=mx;i++)for(int j=1;j<=mx;j++)for(int k=1;k<=mx;k++)sum[i][j][k]+=sum[i-1][j][k];
    int l=1,r=mx,mid,ans;
    while(l<=r){
        mid=(l+r)/2;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}

考察知识点

前缀和，二分答案，容斥

T3 洪水拯救计划（rescue）

50%

要求算出以每个关键点为根的答案，可以枚举根，然后进行一次树形dp计算每次进子树回来与否的代价即可

100%

注意到枚举每个关键点为根时不会错过最优答案，不难发现最优的走法就是dfs，而最优的dfs应该在最深的被拯救的点（以下称为标记点）结束。给出一个简单的证明：因为如果最后要回到原点，那么只要是dfs，不同的走法走过的路程一样，而在最深的点结束可以省下最多回程的路程。因此只需要求出这个点走到其他关键点最远的距离是多少，减去最远距离即可

详细题解补充：

Part 0 ：引入

这道题目有一个很明显的特征：要求算出以每个点为根的答案，而且显然不能枚举，我们可以用运用了一种策略：根的翻转递推（其实是运用了树形dp的思想），也称为换根DP。

不妨回顾一下那道题目，我们通过dfs枚举根，并且把一个点为根的情况通过它的父亲递推得到，其实，这是一种树形dp的策略，只是把dp过程融入到dfs求解当中。这道题是否可以采用类似的策略呢？不妨按照那道题目的步骤一步一步来。

以下，是这道题的树形dp大方向下，从答案结构框架到某部分的计算实现的过程。

Part 1 ：状态转移结论的发现

如果要用这种方法解决问题，包括所有的树形dp问题，我们都必须要知道当根从u转移到u的儿子v时，答案是怎么变化的。

观察这道题目里的答案，不难发现最优的走法就是dfs，而最优的dfs应该在最深的被拯救的点（以下称为标记点）结束。给出一个简单的证明：因为如果最后要回到原点，那么只要是dfs，不同的走法走过的路程一样，而在最深的点结束可以省下最多回程的路程。而从这个证明中，我们实际上已经把答案拆分成两部分：回到原点走过的路程和，减去最深（在根为基地的意义下，下同）的标记点到根的距离，即深度。

Part 2 ：计算路程和

通过树形dp，最深的点的深度可以树形dp出来（下面再讲），而回到原点走过的路程len和是可以O（1）递推的。我们知道，一条边被经过，当且仅当（当根为基地时）它的子树中有至少一个标记点。所以，如果根从u转移到它的儿子v，那么边u-v分3种情况讨论（以下情况中，根为1）：

v的子树中没有标记点，那么这条边本来不用走，现在要走了，所以len加上这条边长的两倍。
v的子树中有所有标记点，即在v的子树外没有标记点，那么这条边本来要走，现在不用走，len减去这条边长的两倍。
其他情况，len不变。

除此之外，没有其它遗漏。我们解决了len的计算问题。

Part 3 ：树形dp求最深点深度

那么，本题的难点就只有一个，就是求最深点深度了。这是一个经典问题，而且我猜应该有不少解决的方法。这里提供我的一种树形dp思路。

在遇到这种求一个点和其它所有点关系的时候，有一种常见的套路，就是把这个问题拆分为（以某个固定点，如1为根的）子树内+子树外两种，先处理子树内，再用父亲的子树内和子树外算出儿子的子树外。这道题，子树内的最深点深度很好计算，一次dfs收集上来最深的深度就可以，关键是求这个点到子树外标记点的最远距离。回到那个套路中，这里我们可以从它的父亲节点的信息来推。

考察节点u，有c个儿子v1,v2,...,vc。那么，对于儿子vi，它子树外的最远距离有两种来源：来自u的其他儿子的子树内和u的子树外。u的子树外已经算出来了，只要加上边u-v，而u的其他儿子的子树内信息也已经算好（因为先算子树内），只要一遍扫过来，记录最大值、次大值（如果最大值取在vi上，要用次大值），然后加上边u-v。这样，两部分就都能够求解了。

另外注意初始值：对于子树内，如果这个点被标记取0，否则取-infty；对于子树外，如果父亲被标记取边u-v，否则取-infty。

Part 4 ：代码组织与实现

这个部分，直接上代码。

#include<cstdio>
#include<algorithm>
using namespace std;
const int M=5e5+5;
void qread(int &r) {//IO数据很大啊，用读入挂可能会好一点
    r=0;
    char c=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')r=(r<<1)+(r<<3)+(c^48),c=getchar();
}
int n,m;
struct edge {
    int v,c,to;
} E[M<<1];
int head[M],tot;
void Link(int u,int v,int c) {
    E[++tot]=(edge) {
        v,c,head[u]
    };
    head[u]=tot;
}
bool mark[M];
long long dis[M],len,sz[M];
long long from_f[M],from_s[M];
void dfs_Init(int u,int f) {//这一次dfs预处理很多东西
    if(mark[u])sz[u]=1,from_s[u]=0;
    else sz[u]=0,from_s[u]=-2e18;
    for(int i=head[u]; i!=0; i=E[i].to) {
        int v=E[i].v,c=E[i].c;
        if(v==f)continue;
        dis[v]=dis[u]+c;//深度
        dfs_Init(v,u);
        sz[u]+=sz[v];//子树内标记点数量
        if(sz[v]>0)len+=c*2;//len在根为1时的初始值
        from_s[u]=max(from_s[u],from_s[v]+c);//子树内深度
    }
}
void re_dfs_Init(int u,int f) {
    long long fir=-2e18,sec=-2e18;//最大值First，次大值Second
    for(int i=head[u]; i!=0; i=E[i].to) {
        int v=E[i].v,c=E[i].c;
        if(v==f)continue;
        long long Dis=from_s[v]+c;
        if(Dis>fir)sec=fir,fir=Dis;
        else if(Dis>sec)sec=Dis;
    }
    for(int i=head[u]; i!=0; i=E[i].to) {
        int v=E[i].v,c=E[i].c;
        if(v==f)continue;
        long long Dis=from_s[v]+c;
        if(Dis==fir)from_f[v]=max(from_f[u],sec)+c;//最大值以外的最大值是次大值
        else from_f[v]=max(from_f[u],fir)+c;
        if(mark[u])from_f[v]=max(from_f[v],(long long)c);//这里注意父亲被标记的情况（实测，比较难拍出来）
        re_dfs_Init(v,u);
    }
}
long long Ans[M];
void dfs_Solve(int u,int f,long long len) {
    Ans[u]=len-max(from_f[u],from_s[u]);
    for(int i=head[u]; i!=0; i=E[i].to) {
        int v=E[i].v,c=E[i].c;
        if(v==f)continue;
        long long nxt_len=len;
        if(sz[v]==0)nxt_len+=c*2;//这里是len的O(1)递推转移
        else if(sz[v]==m)nxt_len-=c*2;
        dfs_Solve(v,u,nxt_len);
    }
}
void Solve() {
    dfs_Init(1,-1);
    if(!mark[1])from_f[1]=-2e18;
    re_dfs_Init(1,-1);
    dfs_Solve(1,-1,len);
    for(int i=1; i<=n; i++)printf("%lld\n",Ans[i]);
}
int main() {
    freopen("rescue.in", "r", stdin);
    freopen("rescue.out", "w", stdout);
    scanf("%d%d",&n,&m);
    for(int i=1; i<n; i++) {
        int u,v,c;
        qread(u),qread(v),qread(c);
        Link(u,v,c);
        Link(v,u,c);
    }
    for(int i=1; i<=m; i++) {
        int u;
        qread(u);
        mark[u]=true;
    }
    Solve();
    return 0;
}

考察知识点

换根DP，树的直径

T4 最短路（path）

题目大意

给定一张有 $n$ 个点， $m$ 条边的无向图，对于每个 $i\in(1,n]$ ，请求出在不经过原来 $1$ 点到 $i$ 节点最短路上最后一条边的前提下的新最短路。

特别地，保证 $1$ 到任何一个点的最短路都是唯一的。

20%

注意到性质 特别地，保证 $1$ 到任何一个点的最短路都是唯一的

此性质与树中：任意两点间路径唯一相似

因此我们可以先跑一次最段路找出每个点最短路上最后一条边，对于每个点手动 ban 掉它，再跑 Dijkstra 算最短路，时间复杂度 $O(nm \log m)$ 。

100%

所以考虑建立最短路树，以1为根节点。（补充，若最短路不唯一则建立的是最短路图）

如果把点 $i$ 到它父亲的边断了怎么办？为了到达，我们需要一条边连接 $i$ 的子树内任意一节点，和子树外任意一节点。

这样思考，似乎很难处理。我们不妨转换角度：

对于任意一条非树边，它能给哪些点做贡献呢？

显然，要求 $u,v$ 在不同子树内。于是，这个子树的根必须在 $u,v$ 的路径上（不含 LCA ）。

那，对路径上的这些点的贡献是多少呢？

我们思考，假设当前节点为 $k$ ，本来它应该是 $1 \rightarrow k$ 的最短路，现在变成了 $1 \rightarrow u \rightarrow v \rightarrow k$ 了。

树上问题，我们常用的手段是把路径转化为到的路径。

于是，$1 \rightarrow u \rightarrow v \rightarrow k = (u \rightarrow v) + (u \rightarrow 1) + (v \rightarrow 1) - (k \rightarrow 1)$ 。其中 $u \rightarrow v$ ，是当前枚举的非树边边权。

这里推荐画图辅助理解。

我们发现， $(k \rightarrow 1)$ 是定值，而$(u \rightarrow v) , (u \rightarrow 1) , (v \rightarrow 1)$ 均只和当前的非树边 $(u,v)$ 有关。因此，我们可以对于每条非树边算出刚才的式子的值。

我们所求转化为求出删去一个点与他父亲的边，通过非树边走到这个点的新路径长度，每一条非树边会在原树上形成一个环，对于环上的每一个点 $i$ ，可以选取的答案为 $W_环-dis_i$ ，依次处理非树边并更新环上所有的答案即可

于是，一个节点最终答案的大小与更新它的边的最小值有直接关系。

Solution 1

接下来，答案就很显然了：我们树链剖分，然后线段树维护区间最小值即可。时间复杂度 $O(n \log^2 n)$ 。

Solution 2

Solution 1 十分的粗鲁：直接用数据结构解决了，但是双 $\log$ 。能不能用更简单的方法呢？

我们发现，一个点被一条边权最小的边更新之后，就不会再被更新了。于是考虑对边按照其对应值进行从小到大排序，每条边暴力找路径，更新答案，但是每次更新完一个点，就把他删掉。删掉？就是下次访问它，直接跳到它的最近没被删的祖先。这让我们想到并查集路径压缩。于是，这道题被优雅解决了，时间复杂度 $O(n)$ 左右。

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}
    return x*w;
}
const int MAXN=2e5;
int n,m;
int dis[MAXN+10],vis[MAXN+10];
int fa[MAXN+10],dep[MAXN+10];
struct A{
	int to,w;
};
vector<A> g[MAXN];
void dij(int s){
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
    q.push(make_pair(0,s));
    memset(dis,0x3f3f3f3f,sizeof(dis));
    dis[s]=0;dep[s]=0;
    while(!q.empty()){
      pair<int,int> ex=q.top();q.pop();
      if(vis[ex.second])continue;
      vis[ex.second]=1;
      for(int i=0;i<g[ex.second].size();i++){
        int v=g[ex.second][i].to,w=g[ex.second][i].w;
        if(!vis[v]&&dis[v]>dis[ex.second]+w){
          dis[v]=dis[ex.second]+w;
          fa[v]=ex.second;
          dep[v]=dep[ex.second]+1;
          q.push(make_pair(dis[v],v));
        }
      }
    }
}
int ans[MAXN+10];
void work(int x,int y,int w){
    while(x!=y){
      if(dep[x]<dep[y]){
        swap(x,y);
      }
      ans[x]=min(ans[x],w-dis[x]);
      x=fa[x];
    }
}
int main(){
    freopen("path.in", "r", stdin);
    freopen("path.out", "w", stdout);
    n=read();m=read();
    for(int i=1;i<=m;i++){
      int a=read(),b=read(),c=read();
      g[a].push_back(A{b,c});
      g[b].push_back(A{a,c});
    }
    dij(1);
    memset(ans,0x3f,sizeof(ans));
    for(int i=1;i<=n;i++){
      for(int j=0;j<g[i].size();j++){
        int v=g[i][j].to,w=g[i][j].w;
        if(dis[v]!=dis[i]+w&&dis[i]!=dis[v]+w){
          work(i,v,dis[v]+dis[i]+w);
        }
      }
    }
    for(int i=2;i<=n;i++){
      if(ans[i]==0x3f3f3f3f)printf("-1\n");
      else printf("%d\n",ans[i]);
    }
	return 0;
}

考察知识点

最短路，树链剖分，并查集，贡献

# 2024暑期CSP-S&NOIP模拟赛第1套题解

## T1 弹钢琴（piano）

### 30-70%

如果音 $a_i$ 能弹对，则说明 $a_i-a_1=b_ik$。其中 $b_i=\left\{\begin{matrix}
 b_{i-1}+1 & a_i>a_{i-1} \\
 b_{i-1} & a_i=a_{i-1} \\
 b_{i-1}-1 & a_i<a_{i-1}
\end{matrix}\right.$  且 $b_1=0$。

枚举与$a_1$匹配的$a_i$，算出对应的$k$，然后对于剩余的去check算出的$k$是否符合要求取$max$即可，时间复杂度$O(n^2)$

### 100%

观察$a_i-a_1=b_ik$，发现已知$i$时$k$是唯一确定的，那么其实可以从每个$k$考虑对答案的贡献即可避免之前做法的check，记 $c_k$ 表示确定 $k$ 后能弹对多少个音。初始 $c_i$ 均为 $1$（$a_1$ 均能弹对）。

由 $2$ 到 $n$ 递推。如果音 $a_i$ 弹对了，那么：

- 若 $b_i=a_i-a_1=0$，所有 $c_k$ 均加一。
- 若 $b_i$ 与 $a_i-a_1$ 异号或 $b_i=0$ 且 $a_i\neq a_1$，那么对 $c_k$ 无贡献。
- 若 $(a_i-a_1)\bmod b_i\neq0$，也对 $c_k$ 无贡献。
- 否则，记 $p=\dfrac{a_i-a_1}{b_i}$，$c_p$ 加一，即$k=p$时的贡献加一。

递推过程中更新并记录即可。

时间复杂度 $O(n)$。

```cpp
#include<bits/stdc++.h>
#include<unordered_map>
#define int long long
using namespace std;
const int N=1e6+10;
int a[N],b[N];
int n,tag,ans, pos;
unordered_map<int,int> num;
signed main(){
    freopen("piano.in", "r", stdin);
    freopen("piano.out", "w", stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=2;i<=n;i++){
        if(a[i]>a[i-1])
            b[i]=b[i-1]+1;
        else if(a[i]==a[i-1])
            b[i]=b[i-1];
        else b[i]=b[i-1]-1;
        int r=a[i]-a[1], q=b[i];
        int npos;
        if(q==0){
            if(r==0) ++tag,npos=pos;
            else continue;
        }
        else if(r==0) ++num[0],npos=0;
        else if(r<0&&q<0){
            r=-r;q=-q;
            if(r%q==0) ++num[r/q],npos=r/q;
        }
        else if((r<0&&q>0)||(r>0&&q<0))
            continue;
        else if(r%q==0) ++num[r/q],npos=r/q;
        if(ans==num[npos]+tag) pos=min(pos,npos);
        else if(ans<num[npos]+tag){
            ans=num[npos]+tag;
            pos=npos;
        }
    }
    cout<<ans+1<<'\n'<<pos;
    return 0;
}
```

### 考察知识点

桶，计数

## T2 选彩笔（rgb）

可以从一维二纬的情况开始考虑

### 50%

发现RGB范围很小，可以考虑把RGB堪称三维空间，枚举一个长度（Colorfulness 值）再枚举答案组里RGB三个坐标的最大值，去这个空间里check是否存在k个点，时间复杂度约为$O(R^7),R$为RGB的值域范围。

### 80%

枚举一个长度后发现check空间里是否存在k个点能通过三维前缀和+容斥维护得到，时间复杂度降为$O(R^4),R$为RGB的值域范围。

### 100%

观察到题目要求差值最大值最小，注意到答案具有二分性，可以考虑二分 长度。 枚举 R,G,B 的最大值，计算在 R 值在区间 $[maxr-mid,maxr]$ 内，G 值在区间 $[maxg-mid,maxg]$ 内，B 值在区间 $[maxb-mid,maxb]$ 内的笔的个数。定义 $sum[i][j][k]$ R 值在区间 $[1,i]$ 内，G 值在区间 $[1,j]$ 内，B 值在区间 $[1,k]$ 内的笔的个数，可以通过三维前缀和求解。 时间复杂度降为$O(R^3 \log R),R$为RGB的值域范围。

代码如下：

```c++
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100010][3],mx;
int sum[300][300][300];
int ct[3];
int rs(int x,int y,int z,int len){
    int rt=sum[x][y][z];
    rt-=(sum[x-len-1][y][z]+sum[x][y-len-1][z]+sum[x][y][z-len-1]);
    rt+=(sum[x-len-1][y-len-1][z]+sum[x-len-1][y][z-len-1]+sum[x][y-len-1][z-len-1]);
    rt-=sum[x-len-1][y-len-1][z-len-1];
    return rt;
}
bool check(int l){
    for(int i=l+1;i<=mx;i++){
        for(int j=l+1;j<=mx;j++){
            for(int k=l+1;k<=mx;k++){
                if(rs(i,j,k,l)>=m){
                    ct[0]=i;
                    ct[1]=j;
                    ct[2]=k;
                    return 1;
                }
            }
        }
    }
    return 0;
}
int main(){
    freopen("rgb.in", "r", stdin);
    freopen("rgb.out", "w", stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
        a[i][0]++;//为了避免边界情况讨论，整体增加一
        a[i][1]++;
        a[i][2]++;
        mx=max(mx,a[i][0]);
        mx=max(mx,a[i][1]);
        mx=max(mx,a[i][2]);
        sum[a[i][0]][a[i][1]][a[i][2]]++;
    }
    for(int i=1;i<=mx;i++)for(int j=1;j<=mx;j++)for(int k=1;k<=mx;k++)sum[i][j][k]+=sum[i][j][k-1];
    for(int i=1;i<=mx;i++)for(int k=1;k<=mx;k++)for(int j=1;j<=mx;j++)sum[i][j][k]+=sum[i][j-1][k];
    for(int i=1;i<=mx;i++)for(int j=1;j<=mx;j++)for(int k=1;k<=mx;k++)sum[i][j][k]+=sum[i-1][j][k];
    int l=1,r=mx,mid,ans;
    while(l<=r){
        mid=(l+r)/2;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}
```

### 考察知识点

前缀和，二分答案，容斥

## T3 洪水拯救计划（rescue）

### 50%

要求算出以每个关键点为根的答案，可以枚举根，然后进行一次树形dp计算每次进子树回来与否的代价即可

### 100%

注意到枚举每个关键点为根时不会错过最优答案，不难发现最优的走法就是dfs，而最优的dfs应该在最深的被拯救的点（以下称为标记点）结束。给出一个简单的证明：因为如果最后要回到原点，那么只要是dfs，不同的走法走过的路程一样，而在最深的点结束可以省下最多回程的路程。因此只需要求出这个点走到其他关键点最远的距离是多少，减去最远距离即可

### 详细题解补充：

### Part 0 ： 引入

这道题目有一个很明显的特征：要求算出以每个点为根的答案，而且显然不能枚举，我们可以用运用了一种策略：根的翻转递推（其实是运用了树形dp的思想），也称为换根DP。

不妨回顾一下那道题目，**我们通过dfs枚举根，并且把一个点为根的情况通过它的父亲递推得到**，其实，这是一种树形dp的策略，只是把dp过程融入到dfs求解当中。这道题是否可以采用类似的策略呢？不妨按照那道题目的步骤一步一步来。

以下，是这道题的树形dp大方向下，从答案结构框架到某部分的计算实现的过程。

### Part 1 ： 状态转移结论的发现

如果要用这种方法解决问题，包括所有的树形dp问题，我们都必须要知道当根从u转移到u的儿子v时，答案是怎么变化的。

观察这道题目里的答案，不难发现最优的走法就是dfs，而最优的dfs应该在最深的被拯救的点（以下称为标记点）结束。给出一个简单的证明：因为如果最后要回到原点，那么只要是dfs，不同的走法走过的路程一样，而在最深的点结束可以省下最多回程的路程。而从这个证明中，我们实际上已经把答案拆分成两部分：回到原点走过的路程和，减去最深（在根为基地的意义下，下同）的标记点到根的距离，即深度。

### Part 2 ： 计算路程和

通过树形dp，最深的点的深度可以树形dp出来（下面再讲），而回到原点走过的路程len和是可以O（1）递推的。我们知道，一条边被经过，当且仅当（当根为基地时）它的子树中有至少一个标记点。所以，如果根从u转移到它的儿子v，那么边u-v分3种情况讨论（以下情况中，根为1）：

1. v的子树中没有标记点，那么这条边本来不用走，现在要走了，所以len加上这条边长的两倍。
2. v的子树中有所有标记点，即在v的子树外没有标记点，那么这条边本来要走，现在不用走，len减去这条边长的两倍。
3. 其他情况，len不变。

除此之外，没有其它遗漏。我们解决了len的计算问题。

### Part 3 ： 树形dp求最深点深度

那么，本题的难点就只有一个，就是求最深点深度了。这是一个经典问题，而且我猜应该有不少解决的方法。这里提供我的一种树形dp思路。

在遇到这种求一个点和其它所有点关系的时候，有一种常见的套路，就是把这个问题拆分为（以某个固定点，如1为根的）子树内+子树外两种，先处理子树内，再用父亲的子树内和子树外算出儿子的子树外。这道题，子树内的最深点深度很好计算，一次dfs收集上来最深的深度就可以，关键是求这个点到子树外标记点的最远距离。回到那个套路中，这里我们可以从它的父亲节点的信息来推。

考察节点u，有c个儿子v1,v2,...,vc。那么，对于儿子vi，它子树外的最远距离有两种来源：来自u的其他儿子的子树内和u的子树外。u的子树外已经算出来了，只要加上边u-v，而u的其他儿子的子树内信息也已经算好（因为先算子树内），只要一遍扫过来，记录最大值、次大值（如果最大值取在vi上，要用次大值），然后加上边u-v。这样，两部分就都能够求解了。

另外注意初始值：对于子树内，如果这个点被标记取0，否则取-infty；对于子树外，如果父亲被标记取边u-v，否则取-infty。

### Part 4 ： 代码组织与实现

这个部分，直接上代码。

```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int M=5e5+5;
void qread(int &r) {//IO数据很大啊，用读入挂可能会好一点
    r=0;
    char c=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')r=(r<<1)+(r<<3)+(c^48),c=getchar();
}
int n,m;
struct edge {
    int v,c,to;
} E[M<<1];
int head[M],tot;
void Link(int u,int v,int c) {
    E[++tot]=(edge) {
        v,c,head[u]
    };
    head[u]=tot;
}
bool mark[M];
long long dis[M],len,sz[M];
long long from_f[M],from_s[M];
void dfs_Init(int u,int f) {//这一次dfs预处理很多东西
    if(mark[u])sz[u]=1,from_s[u]=0;
    else sz[u]=0,from_s[u]=-2e18;
    for(int i=head[u]; i!=0; i=E[i].to) {
        int v=E[i].v,c=E[i].c;
        if(v==f)continue;
        dis[v]=dis[u]+c;//深度
        dfs_Init(v,u);
        sz[u]+=sz[v];//子树内标记点数量
        if(sz[v]>0)len+=c*2;//len在根为1时的初始值
        from_s[u]=max(from_s[u],from_s[v]+c);//子树内深度
    }
}
void re_dfs_Init(int u,int f) {
    long long fir=-2e18,sec=-2e18;//最大值First，次大值Second
    for(int i=head[u]; i!=0; i=E[i].to) {
        int v=E[i].v,c=E[i].c;
        if(v==f)continue;
        long long Dis=from_s[v]+c;
        if(Dis>fir)sec=fir,fir=Dis;
        else if(Dis>sec)sec=Dis;
    }
    for(int i=head[u]; i!=0; i=E[i].to) {
        int v=E[i].v,c=E[i].c;
        if(v==f)continue;
        long long Dis=from_s[v]+c;
        if(Dis==fir)from_f[v]=max(from_f[u],sec)+c;//最大值以外的最大值是次大值
        else from_f[v]=max(from_f[u],fir)+c;
        if(mark[u])from_f[v]=max(from_f[v],(long long)c);//这里注意父亲被标记的情况（实测，比较难拍出来）
        re_dfs_Init(v,u);
    }
}
long long Ans[M];
void dfs_Solve(int u,int f,long long len) {
    Ans[u]=len-max(from_f[u],from_s[u]);
    for(int i=head[u]; i!=0; i=E[i].to) {
        int v=E[i].v,c=E[i].c;
        if(v==f)continue;
        long long nxt_len=len;
        if(sz[v]==0)nxt_len+=c*2;//这里是len的O(1)递推转移
        else if(sz[v]==m)nxt_len-=c*2;
        dfs_Solve(v,u,nxt_len);
    }
}
void Solve() {
    dfs_Init(1,-1);
    if(!mark[1])from_f[1]=-2e18;
    re_dfs_Init(1,-1);
    dfs_Solve(1,-1,len);
    for(int i=1; i<=n; i++)printf("%lld\n",Ans[i]);
}
int main() {
    freopen("rescue.in", "r", stdin);
    freopen("rescue.out", "w", stdout);
    scanf("%d%d",&n,&m);
    for(int i=1; i<n; i++) {
        int u,v,c;
        qread(u),qread(v),qread(c);
        Link(u,v,c);
        Link(v,u,c);
    }
    for(int i=1; i<=m; i++) {
        int u;
        qread(u);
        mark[u]=true;
    }
    Solve();
    return 0;
}
```

### 考察知识点

换根DP，树的直径

## T4 最短路（path）

### 题目大意

给定一张有$n$个点，$m$条边的无向图，对于每个$i\in(1,n]$，请求出在不经过原来$1$点到$i$节点最短路上最后一条边的前提下的新最短路。

特别地，保证$1$到任何一个点的最短路都是唯一的。

### 20%

注意到性质 **特别地，保证$1$到任何一个点的最短路都是唯一的**

此性质与树中：任意两点间路径唯一相似

因此我们可以先跑一次最段路找出每个点最短路上最后一条边，对于每个点手动 ban 掉它，再跑 Dijkstra 算最短路，时间复杂度$O(nm \log m)$ 。

### 100%

所以考虑建立**最短路树**，以1为根节点。（补充，若最短路不唯一则建立的是最短路图）

如果把点$i$到它父亲的边断了怎么办？为了到达 ，我们需要一条边连接$i$的子树内任意一节点，和子树外任意一节点。

这样思考，似乎很难处理。我们不妨转换角度：

对于任意一条非树边 ，它能给哪些点做贡献呢？

显然，要求$u,v$在不同子树内。于是，这个子树的根必须在$u,v$的路径上（不含 LCA ）。

那，对路径上的这些点的贡献是多少呢？

我们思考，假设当前节点为$k$，本来它应该是 $1 \rightarrow k$ 的最短路，现在变成了$1 \rightarrow u \rightarrow v \rightarrow k$了。

树上问题，我们常用的手段是**把路径转化为到 的路径**。

于是，$1 \rightarrow u \rightarrow v \rightarrow k = (u \rightarrow v) + (u \rightarrow 1) + (v  \rightarrow 1) - (k \rightarrow 1)$ 。其中$u \rightarrow v$， 是当前枚举的非树边边权。

这里推荐画图辅助理解。

我们发现， $(k \rightarrow 1)$是定值，而$(u \rightarrow v) , (u \rightarrow 1) , (v  \rightarrow 1)$ 均只和当前的非树边$(u,v)$有关。因此，我们可以对于每条非树边算出刚才的式子的值。

我们所求转化为求出删去一个点与他父亲的边，通过非树边走到这个点的新路径长度，每一条非树边会在原树上形成一个环，对于环上的每一个点$i$，可以选取的答案为$W_环-dis_i$，依次处理非树边并更新环上所有的答案即可

于是，一个节点最终答案的大小与更新它的边的最小值有直接关系。

### Solution 1

接下来，答案就很显然了：我们树链剖分，然后线段树维护区间最小值即可。时间复杂度$O(n \log^2 n)$ 。

### Solution 2

Solution 1 十分的粗鲁：直接用数据结构解决了，但是双$\log$ 。能不能用更简单的方法呢？

我们发现，一个点被一条边权最小的边更新之后，就不会再被更新了。于是考虑**对边按照其对应值进行从小到大排序**，每条边暴力找路径，更新答案，但是**每次更新完一个点，就把他删掉**。删掉？就是下次访问它，直接跳到它的最近没被删的祖先。这让我们想到**并查集路径压缩**。于是，这道题被优雅解决了，时间复杂度$O(n)$左右。

```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}
    return x*w;
}
const int MAXN=2e5;
int n,m;
int dis[MAXN+10],vis[MAXN+10];
int fa[MAXN+10],dep[MAXN+10];
struct A{
	int to,w;
};
vector<A> g[MAXN];
void dij(int s){
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
    q.push(make_pair(0,s));
    memset(dis,0x3f3f3f3f,sizeof(dis));
    dis[s]=0;dep[s]=0;
    while(!q.empty()){
      pair<int,int> ex=q.top();q.pop();
      if(vis[ex.second])continue;
      vis[ex.second]=1;
      for(int i=0;i<g[ex.second].size();i++){
        int v=g[ex.second][i].to,w=g[ex.second][i].w;
        if(!vis[v]&&dis[v]>dis[ex.second]+w){
          dis[v]=dis[ex.second]+w;
          fa[v]=ex.second;
          dep[v]=dep[ex.second]+1;
          q.push(make_pair(dis[v],v));
        }
      }
    }
}
int ans[MAXN+10];
void work(int x,int y,int w){
    while(x!=y){
      if(dep[x]<dep[y]){
        swap(x,y);
      }
      ans[x]=min(ans[x],w-dis[x]);
      x=fa[x];
    }
}
int main(){
    freopen("path.in", "r", stdin);
    freopen("path.out", "w", stdout);
    n=read();m=read();
    for(int i=1;i<=m;i++){
      int a=read(),b=read(),c=read();
      g[a].push_back(A{b,c});
      g[b].push_back(A{a,c});
    }
    dij(1);
    memset(ans,0x3f,sizeof(ans));
    for(int i=1;i<=n;i++){
      for(int j=0;j<g[i].size();j++){
        int v=g[i][j].to,w=g[i][j].w;
        if(dis[v]!=dis[i]+w&&dis[i]!=dis[v]+w){
          work(i,v,dis[v]+dis[i]+w);
        }
      }
    }
    for(int i=2;i<=n;i++){
      if(ans[i]==0x3f3f3f3f)printf("-1\n");
      else printf("%d\n",ans[i]);
    }
	return 0;
}
```

### 考察知识点

最短路，树链剖分，并查集，贡献

我们会审查剪贴板内容，并对发布不合适内容的同学进行相应的处理

题解

2024暑期CSP-S&NOIP模拟赛第1套题解

T1 弹钢琴（piano）

30-70%

100%

考察知识点

T2 选彩笔（rgb）

50%

80%

100%

考察知识点

T3 洪水拯救计划（rescue）

50%

100%

详细题解补充：

Part 0 ： 引入

Part 1 ： 状态转移结论的发现

Part 2 ： 计算路程和

Part 3 ： 树形dp求最深点深度

Part 4 ： 代码组织与实现

考察知识点

T4 最短路（path）

题目大意

20%

100%

Solution 1

Solution 2

考察知识点

SIGN IN

Part 0 ：引入

Part 1 ：状态转移结论的发现

Part 2 ：计算路程和

Part 3 ：树形dp求最深点深度

Part 4 ：代码组织与实现