总结 | 2022牛客OI赛前集训营-提高组（第二场）总结

T1 躲避技能

估分 $100pts100pts$，实际 $0pts0pts$。

题目大意

在 $nn$ 个点的树上有 $mm$ 个起点和终点，将其两两配对形成 $mm$ 个点对，使得每个点对之间的距离和最小

解题思路

枚举全排列可得 40pts，网络流可以在 $O(n^3)O(n^3)$ 的时间复杂度内完成。

想要 A 掉这一题，需要时间复杂度在 $O(n\log n)O(n\backslash log\; n)$ 一下的算法。

要求最优解，我们有两个方向可以思考：一是构造最优解，如构造，一般的动态规划；二是先跑一遍任意解，并通过答案计算出最优解，如换根 DP。显然这一题更加适合后一种方法。

从样例入手，先把题目给的树画出来：

既然一开始先跑任意解，我们不妨就按照题目给的顺序两两配对，并写出其经过的边（有向）：

5 ——> 1 ——> 2 ——> 4
1 ——> 2
3 ——> 2 ——> 1
2

然后来考虑如何得到最优解。我们可以手推出其中一种最优解：

5 ——> 1 ——> 2 ——> 4
1
3 ——> 2
2

最优解经过的边正好比一开始跑的少了一条 $(1,2)(1,2)$ 和一条 $(2,1)(2,1)$ 的边。于是我们可以猜测一个结论，如果一条边被正向经过一次再被反向经过一次，这条边就不用记录贡献。

为什么呢，我们还是拿样例来说明。由于只有 $11$ 和 $33$ 为起点的路径发生了改变，所以只分析它们。我们在他们上面分别放上完全相同的棋子 $aa$ 和 $bb$ 来模拟移动的过程。

按照最初的任意解，我们先把 $aa$ 位置移动到 $22$，同时 $bb$ 也移动到 $22$。接着，$aa$ 移动到 $44$，$bb$ 移动到 $11$。

但是注意，由于棋子 $aa$ 和 $bb$ 是完全相同的，所以不论最终是 $aa$ 在 $44$ 上，$bb$ 在 $11$ 上还是 $aa$ 在 $11$ 上，$bb$ 在 $44$ 上，都没有问题。

所以 $aa$ 移动到 $44$，$bb$ 移动到 $11$ 可以看成 $aa$ 后退回到 $11$，而 $bb$ 移动到 $44$。

那既然 $aa$ 后退回到 $aa$，其实就相当于一开始并没有移动到 $22$，而是一直待在 $11$。那么 $(1,2)(1,2)$ 和 $(2,1)(2,1)$ 这两条边就没必要加了。

至于实现，我这里使用树链剖分来实现。由于是在树上，所以我们可以定“正向”为向深度较小的结点的方向，“反向”为向深度较大的结点的方向，并且我们可以用结点代替它和它父亲之间的边。对于一个起点和一个终点，我们是先从起点“正向”走到 $lcalca$，再从 $lcalca$ 反向走到终点。对从起点到 $lcalca$ 路径上的点，我们给它们的点权加上 $11$；对于从 $lcalca$ 到终点路径上的点，我们给它们的点权加上 $-1-1$。最后枚举所有结点，将答案加上它的点权的绝对值乘上它所代表的边的边权。

代码如下：

#include<bits/stdc++.h>
#define MAXL 110
#define MAXN 100010
#define lson now << 1
#define rson now << 1 | 1
using namespace std;
struct big_num{
    int len,val[MAXL];
    bool is_positive;
    void print_big_num(){
        if(!is_positive) putchar('-');
        for(int i=len;i>=1;i--){
            printf("%d",val[i]);
        }
        printf("\n");
    }
    void scanf_big_num(){
        char ch=getchar();
        int s[MAXL];
        len=0; is_positive=true;
        memset(val, 0, sizeof(val));
        while(ch<'0'||ch>'9'){
            if(ch=='-') is_positive=false;
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            s[++len]=ch-'0';
            ch=getchar();
        }
        for(int i=1;i<=len;i++){
            val[i]=s[i];
        }
    }
    big_num operator + (const big_num &b){
        big_num res;
        memset(res.val,0,sizeof(res.val));
        res.len=max(this->len,b.len);
        if(this->is_positive&&b.is_positive) res.is_positive=true;
        else if((!this->is_positive) && (!b.is_positive)) res.is_positive=false;
        else if((!this->is_positive) && b.is_positive){
            big_num x=*this,y=b; x.is_positive=true;
            res=y-x;
            return res;
        }else if(this->is_positive && (!b.is_positive)){
            big_num x=b; x.is_positive=true;
            res=*this-x;
            return res;
        }
        for(int i=1;i<=res.len;i++){
            res.val[i]=(i > this->len ? 0 : this->val[i]) + (i > b.len ? 0 : b.val[i]);
        }
        for(int i=1;i<=res.len;i++){
            res.val[i+1] += res.val[i]/10;
            res.val[i] %= 10;
        }
        if(res.val[res.len + 1] > 0) res.len++;
        return res;
    }
    big_num operator - (const big_num &b){
        big_num res=*this;
        if(!b.is_positive){
            big_num x=b; x.is_positive=true;
            return *this+x;
        }
        if(!res.is_positive){
            res.is_positive=true;
            res+=b; res.is_positive=!res.is_positive;
            return res;
        }
        if(res<b){
            big_num x=b;
            res=x-res;
            res.is_positive=!res.is_positive;
            return res;
        }
        res.is_positive=true;
        for(int i=1;i<=res.len;i++){
            res.val[i]-=b.val[i];
            if(res.val[i]<0){
                res.val[i]+=10; res.val[i+1]--;
            }
        }
        while(res.val[res.len]==0&&res.len>0) res.len--;
        if(res.len<1) res.len++;
        return res;
    }
    big_num operator += (const big_num &b){
        *this=*this+b;
        return *this;
    }
    big_num operator -= (const big_num &b){
        *this=*this-b;
        return *this;
    }
    bool operator < (const big_num &b){
        if(is_positive!=b.is_positive) return is_positive<b.is_positive;
        else if(is_positive&&b.is_positive){
            if(len!=b.len) return len<b.len;
            else{
                for(int i=b.len;i>=1;i--){
                    if(val[i]!=b.val[i]){
                        return val[i]<b.val[i];
                    }
                }
                return false;
            }
        }else{
            big_num x,y;
            x=*this; y=b;
            x.is_positive=y.is_positive=true;
            return x>y;
        }
    }
    bool operator > (const big_num &b){
        if(is_positive!=b.is_positive) return is_positive>b.is_positive;
        else if(is_positive&&b.is_positive){
            if(len!=b.len) return len>b.len;
            else{
                for(int i=b.len;i>=1;i--){
                    if(val[i]!=b.val[i]){
                        return val[i]>b.val[i];
                    }
                }
                return false;
            }
        }else{
            big_num x,y;
            x=*this; y=b;
            x.is_positive=y.is_positive=true;
            return x<y;
        }
    }
    bool operator == (const big_num &b){
        if(len!=b.len||is_positive!=b.is_positive) return false;
        else{
            for(int i=b.len;i>=1;i--){
                if(val[i]!=b.val[i]){
                    return false;
                }
            }
            return true;
        }
    }
    bool operator < (const int &x){
        big_num b; b=x;
        return *this<b;
    }
    bool operator > (const int &x){
        big_num b; b=x;
        return *this>b;
    }
    bool operator == (const int &x){
        big_num b; b=x;
        return *this==b;
    }
    bool operator = (const int &x){
        int num=x;
        if(num>=0) is_positive=true;
        else is_positive=false;
        if(x==0) len=1,val[1]=0;
        else{
            len=0; num=abs(num);
            memset(val,0,sizeof(val));
            while(num>0){
                val[++len]=num%10;
                num/=10;
            }
        }
        return true;
    }
};
typedef big_num ll;
struct edge{ int pre, to; ll w; };
struct node{
    int l, r;
    int res, lazy_tag;
};
edge e[MAXN << 1];
node tree[MAXN << 2];
int n, m, cnt, dfc;
int s[MAXN], t[MAXN], fa[MAXN][25], dep[MAXN], head[MAXN], pos[MAXN], top[MAXN], son[MAXN], siz[MAXN];
ll dis[MAXN];
void dfs(int now){
    for(int i = head[now]; i; i = e[i].pre){
        if(e[i].to == fa[now][0]) continue;
        fa[e[i].to][0] = now;
        dep[e[i].to] = dep[now] + 1;
        dis[e[i].to] = dis[now] + e[i].w;
        dfs(e[i].to);
    }
}
int get_lca(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    for(int i = 20; i >= 0; i--){
        if(dep[fa[u][i]] >= dep[v]) u = fa[u][i];
    }
    if(u == v) return v;
    for(int i = 20; i >= 0; i--){
        if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
    }
    return fa[u][0];
}
ll get_dis(int u, int v){
    int lca = get_lca(u, v);
    return dis[u] - dis[lca] + dis[v] - dis[lca];
}

void dfs1(int now){
    siz[now] = 1;
    for(int i = head[now]; i; i = e[i].pre){
        if(e[i].to == fa[now][0]) continue;
        dfs1(e[i].to);
        siz[now] += siz[e[i].to];
        if(siz[e[i].to] > siz[son[now]]) son[now] = e[i].to;
    }
}
void dfs2(int now, int root){
    top[now] = root; pos[now] = ++dfc;
    if(son[now] == 0) return ;
    dfs2(son[now], root);
    for(int i = head[now]; i; i = e[i].pre){
        if(e[i].to == fa[now][0] || e[i].to == son[now]) continue;
        dfs2(e[i].to, e[i].to); 
    }
}

void push_down(int now){
    if(tree[now].lazy_tag){
        tree[lson].lazy_tag += tree[now].lazy_tag;
        tree[rson].lazy_tag += tree[now].lazy_tag;
        tree[lson].res += (tree[lson].r - tree[lson].l + 1) * tree[now].lazy_tag;
        tree[rson].res += (tree[rson].r - tree[rson].l + 1) * tree[now].lazy_tag;
        tree[now].lazy_tag = 0;
    }
}
void push_up(int now){
    tree[now].res = tree[lson].res + tree[rson].res;
}
void build(int now, int l, int r){
    tree[now].l = l; tree[now].r = r;
    if(tree[now].l == tree[now].r) return ;
    int mid = (l + r) >> 1;
    build(lson, l, mid); build(rson, mid + 1, r);
    push_up(now);
}
void update(int now, int l, int r, int val){
    if(tree[now].l >= l && tree[now].r <= r){
        tree[now].lazy_tag += val;
        tree[now].res += (tree[now].r - tree[now].l + 1) * val;
        return ;
    }
    push_down(now);
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(r <= mid) update(lson, l, r, val);
    else if(l > mid) update(rson, l, r, val);
    else update(lson, l, mid, val), update(rson, mid + 1, r, val);
    push_up(now);
}
int query(int now, int pos){
    if(tree[now].l == pos && tree[now].r == pos) return tree[now].res;
    push_down(now);
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(pos <= mid) return query(lson, pos);
    else return query(rson, pos);
}

void install(int u, int v, int val){
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]]) swap(u,v);
        update(1, pos[top[u]], pos[u], val);
        u = fa[top[u]][0];
    }
    if(pos[u] > pos[v]) swap(u, v);
    update(1, pos[u], pos[v], val);
}


void pre_work(){
    dep[1] = 1; dis[1] = 0; dfs(1);
    for(int j = 1; j <= 20; j++){
        for(int i = 1; i <= n; i++){
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
        }
    }
    dfs1(1); dfs2(1, 1); build(1, 1, dfc);
}

void add_edge(int u, int v, ll w){
    e[++cnt].pre = head[u];
    e[cnt].to = v; e[cnt].w = w;
    head[u] = cnt;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m; i++) scanf("%d",&s[i]);
    for(int i = 1; i <= m; i++) scanf("%d",&t[i]);
    for(int i = 1; i < n; i++){
        int u, v; ll w; scanf("%d%d",&u,&v);
        w.scanf_big_num();
        add_edge(u, v, w); add_edge(v, u, w);
    }
    pre_work();
    for(int i = 1; i <= m; i++){
        int lca = get_lca(s[i], t[i]);
        install(s[i], lca, 1); install(lca, t[i], -1);
    }
    ll ans; ans = 0;
    for(int i = 1; i <= n; i++){
        int x = query(1, pos[i]);
        x = abs(x);
        while(x > 0){
            ans += dis[i] - dis[fa[i][0]];
            x--;
        }
    }
    ans.print_big_num();
    return 0;
}

关于 $00$ 分的原因：

泪崩

T2 奶茶兑换券

估分 $0pts0pts$，实际 $0pts0pts$。 比赛的时候没有打，能够想到对 $mm$ 取模后运算，但没有其他思路了。

T3 帮助

估分 $44pts44pts$，实际 $25pts25pts$。 只打暴力，特殊数据的写法有问题，导致还少了 $55$ 分。

T4 神奇的变换

估分 $40pts40pts$，实际 $20pts20pts$。 暴力貌似错了，只拿到 $n=1n\; =\; 1$ 的 $2020$ 分。