NOIP2015 Day2 T3(树上差分序列+LCA)

发表于 | 分类于 | | + s

这题求最大值最小，显然二分。
我们二分本题的答案，如何处理虫洞的情况？
因为只能改造一个虫洞，那么这个虫洞一定是在某些“不改造虫洞会超过二分答案的路径”上，也就是这些路径的交。
那么我们先把每条路径的时间长求出来，怎么求？树上的路径，用LCA即可，时间复杂度$O(mlogn)$
求出来以后，我们每次二分，都一一检查每个路径的时间，如果大于二分答案，就在树上将这一个路径覆盖，那么问题来了，这里怎么覆盖？直接暴力？$O(mn)$的时间复杂度无法接受。这里方法一是树剖后线段树维护，但是这样的代码量直线上升。我们可以考虑差分序列。在线性的数据结构上的差分序列我们已经很熟悉了，$f[a]+1$, $f[b+1]-1$，那么在树上怎么办？很简单，我们让$f[u]+1, f[v]+1, f[LCA(u, v)]-2$，这样做以后在树上的前缀和$\sum_{k\in son(i)}{f[k]}$就表示该点为到其父亲的这条边被经过的次数，之后再找出所有路径的交，判定一下删除的情况就行了，这个地方边权一定要转化为点权。修改在深度深的那个节点上，否则会出现节点未更新完就判断导致错误，代码中有提示。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;

const int MAXN = 300000 + 5, logs = 21, INF = 1000000000;

int n, m, en, dep[MAXN], fa[MAXN], pre[MAXN][logs+1], dis[MAXN], pu[MAXN], pv[MAXN],
pc[MAXN], f[MAXN], lca[MAXN], dwi[MAXN];
vector<int> G[MAXN];
struct edge{int v, wi;}e[MAXN*2];

void ins(int u, int v, int wi) {
    en++, e[en].v = v, e[en].wi = wi, G[u].push_back(en);
}
void clean() {
    en = 0;
    for (int i=0;i<=n;i++) {
        G[i].clear();
        lca[i] = pc[i] = dep[i] = fa[i] = dis[i] = 0;
        for (int j=0;j<=logs;j++) pre[i][j] = 0;
    }
}
void init() {
    clean();
    for (int i=1;i<n;i++) {
        int ai, bi, ti;
        scanf("%d%d%d", &ai, &bi, &ti);
        ins(ai, bi, ti), ins(bi, ai, ti);
    }
    for (int i=1;i<=m;i++) {
        scanf("%d%d", &pu[i], &pv[i]);
    }
}
void dfs1(int u, int pa) {
    dep[u] = dep[pa]+1, fa[u] = pa, pre[u][0] = pa;
    for (int i=1;i<=logs;i++) pre[u][i] = pre[pre[u][i-1]][i-1];
    for (int i=0;i<G[u].size();i++) {
        edge ed = e[G[u][i]];
        int v = ed.v, wi = ed.wi;
        if (v!=pa) {
            dis[v] = dis[u] + wi;
            dwi[v] = wi;
            dfs1(v, u);
        }
    }
}
int LCA(int a, int b) {
    if (dep[a]<dep[b]) swap(a, b);
    for (int i=logs;i>=0;i--) if (dep[pre[a][i]]>=dep[b]) a = pre[a][i];
    if (a==b) return a;
    for (int i=logs;i>=0;i--) if (pre[a][i]!=pre[b][i]) a = pre[a][i], b = pre[b][i];
    return pre[a][0];
}
int max1, max2, tot;
void dfs2(int u, int pa) {
    for (int i=0;i<G[u].size();i++) {
        edge ed = e[G[u][i]];
        int v = ed.v, wi = ed.wi;
        if (v!=pa) {
            dfs2(v, u);
            f[u] += f[v];
        }
    }
    if (f[u]==tot) max2 = max(max2, dwi[u]);
}
bool check(int x) {
    ms(f, 0), tot = max1 = max2 = 0;
    for (int i=1;i<=m;i++) {
        if (pc[i]>x) {
            max1 = max(max1, pc[i]);
            tot++;
            f[lca[i]]-=2;
            f[pu[i]]++, f[pv[i]]++;
        }
    }
    dfs2(1, 0);
    return x>=max1-max2;
}
void solve() {
    dfs1(1, 0);
    int l = 0, r = 300000*1000, ans = INF;
    for (int i=1;i<=m;i++) {
        pc[i] = dis[pu[i]]+dis[pv[i]]-2*dis[lca[i] = LCA(pu[i], pv[i])];
    }
    r++;
    while (l<r) {
        int mid = (l+r)>>1;
        if (check(mid)) {
            ans = mid;
            r = mid;
        } else l = mid + 1;
    }
    printf("%d\n", ans);
}
int main() {
    #ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    while (scanf("%d%d", &n, &m)==2) init(), solve();
    return 0;
}
------ 本文结束 ------