\(\large{T1\ 最大生成树} \ \ \tiny{30 pts}\)

• 题意： 给定一个点权为\(a_i\) 边权为\(|a_i-a_j|\) 的完全图，求这个图的最大生成树
• 部分分：
  • 30~50pts：Kruskal求最长路
• 100pts：贪心，设权值最大点为\(a_{max}\)，权值最小点为\(a_{min}\) 则\(max(|a_{max}-a_i|,|a_{min}-a_i|)\)一定为\(a_i\)的对答案最大贡献

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define int long long
#define frer freopen("in.in","r",stdin);
#define frew freopen("out.out","w",stdout);
using namespace std;
const int Max = 1e5+10;
int n;
int a[Max];
int e[Max];
int m;
int ans;
inline int read(){
    int num=0,fl=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') fl=-1;
            c=getchar();
    }
    while(c >='0'&&c <='9'){
        num=(num<<3)+(num<<1)+(c^48);
        c=getchar();
    }
    return num*fl;
}
inline bool cmp(int a,int b){
    return a>b;
}
signed main(){
    n=read();
    for(int i = 1;i <= n;i++){
        a[i]=read();
    }
    
    sort(a+1,a+n+1,cmp);
    for(int i = 1;i < n;i++){
        e[i]=max(abs(a[1]-a[i]),abs(a[n]-a[i]));
    }
    sort(e+1,e+n+1,cmp);
    for(int i = 1;i < n;i++){
        ans+=e[i];
    }
    printf("%lld",ans);
    return 0;
}

\(\large{T2\ 红黑树} \ \ \tiny{0 pts}\)

• 题意：给定一棵\(n\)个点的有根树，根为节点1，初始每个点都是红色，有次操作，每次操作会把\(p_i\)变成黑色，保证操作序列\(p\)是一个排列，输出有多少个子树是红黑树。
• 部分分：
  • 50pts：每次遍历以每个节点为根的子树（没调出来）。
  • 80pts: 暴力跳爹（没打）
• 100pts: 差分：用\(fir\)记录每个子树第一个黑点出现的时间，用\(fin\)记录每个子树最后一个红点被覆盖的时间。并用差分维护（可以理解为在区间内此子树一直为红黑树）
  • 注意：\(fin\)数组维护差分时为 sum[fin[i]-1+1]，“-1”是因为\(fin[i]\)时此子树已经不是红黑树，“+1”是因为差分。

#include <iostream>
#include <cstdio>
#define int long long
#define frer freopen("in.in","r",stdin);
#define frew freopen("out.out","w",stdout);
using namespace std;
const int Max = 1e5+10;
int n;
int ans,f;
int Head[Max],Next[Max],Ver[Max],tot;
int times[Max];
int fir[Max],fin[Max];
int sum[Max];
inline void add(int x,int y){
    Ver[++tot]=y;Next[tot]=Head[x];Head[x]=tot;
}
inline int read(){
    int num=0,fl=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') fl=-1;
            c=getchar();
    }
    while(c >='0'&&c <='9'){
        num=(num<<3)+(num<<1)+(c^48);
        c=getchar();
    }
    return num*fl;
}
inline void dfs(int x){
    fir[x]=times[x],fin[x]=times[x];
    for(int i = Head[x];i;i=Next[i]){
        int y=Ver[i];
        dfs(y);
        fir[x]=min(fir[x],fir[y]);
        fin[x]=max(fin[x],fin[y]);
    }
}
signed main(){
    frer;
    frew;
    n=read();
    for(int i = 1;i < n;i++){
        int x=read();
        add(x,i+1);
    }
    for(int i = 1;i <= n;i++){
        int x=read();
        times[x]=i;
    }
    dfs(1);
    for(int i = 1;i <= n;i++){
        sum[fir[i]]++;
        sum[fin[i]-1+1]--;
    }
    for(int i = 1;i <= n;i++){
        ans+=sum[i];
        printf("%lld ",ans);
    }
    return 0;
}

\(\large{T3\ 校门外的树} \ \ \tiny{0 pts}\)

• 题意：校门外有\(n\)棵树，每棵树有一个初始高度\(h_i\)和生长速度\(v_i\)，在接下来的\(m\)天中，第\(i\)棵树会长高\(v_i\)，之后有两种事件可能会发生:
  • 操作一：将\([l,r]\)区间内的\(v_i\)增加v。
  • 操作二：求\(\sum_{i=l}^{r} h_i\)
• 部分分：
  • 30pts：数组&&线段树乱搞

\(\large{T4\ 种树} \ \ \tiny{0 pts}\)

• 什么事根号分治？