洛谷 2680 运输计划 题解

发表于 | 更新于 | 阅读次数：
本文字数： 1.4k 字 | 阅读时长 ≈ 7 分钟

题意简述

$n$个点的边带权树，给$m$条关键的链。把树上一条边的权值变为0，使得$m$条链的和中，最大值最小。 $n,m<=1e5$。

思路

二分最大值$k$。现在考虑如何检验一个$k$。

找到所有链和$>k$的链，设这里面最长的链长度为$S$，有$C$条这样的链。用树链剖分找到被所有$C$条链都覆盖的边。设边权为$w$，如果$S-w<=k$，又因为这条边被所有和$>k$的链都覆盖了，所以，将这条边边权设为$0$，就珂以把所有和$>k$的链修♂正回来。那就满足条件了，检验结果为true。

然后就这样二分即珂。

关于如何求被所有链都覆盖的边

如果您足够明智，跳过这个部分好了。

开一颗临时的树，所有边权为$0$，树链剖分维护：对于所有和$>k$的链$(a,b)$，在链上的边权都+1。

然后只要找边权$=C$的边即珂。

但是树链剖分维护的是点权，怎么把边权转化成点权呢？只要把一条边的权值，记录在这条边的儿子上即珂。然后我们对于链$(u,v)$作加法操作的时候，记得把$LCA(u,v)$的操作给撤回掉（就是减掉），因为这个是多算的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197

#include <bits/stdc++.h>using namespace std;
namespace Flandre_Scarlet
{
    #define int long long 
    #define N 355555
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    class Graph //图
    {
        public:
            int head[N];
            int EdgeCount;
            struct Edge
            {
                int To,Label,Next;
            }Ed[N<<1];
            void clear(int _V=N,int _E=N<<1) 
            {
                memset(Ed,-1,sizeof(Edge)*(_E));
                memset(head,-1,sizeof(int)*(_V));
                EdgeCount=-1;
            }
            void AddEdge(int u,int v,int w=1)
            {
                Ed[++EdgeCount]=(Edge){v,w,head[u]};
                head[u]=EdgeCount;
            }
            void Add2(int u,int v,int w=1) {AddEdge(u,v,w);AddEdge(v,u,w);}
            int Start(int u) {return head[u];}
            int To(int u){return Ed[u].To;}
            int Label(int u){return Ed[u].Label;}
            int Next(int u){return Ed[u].Next;}
    }G;
    class BIT //树状数组
    {
        public:
            int tree[N];
            int len;
            void BuildTree(int _len)
            {
                len=_len;
                FK(tree);
            }
            void Add(int pos,int val=1)
            {
                for(int i=pos;i<=len;i+=(i&(-i)))
                {
                    tree[i]+=val;
                }
            }
            void RAdd(int l,int r,int val=1) {Add(l,val);Add(r+1,-val);}
            int Query(int pos)
            {
                int ans=0;
                for(int i=pos;i>0;i-=(i&(-i)))
                {
                    ans+=tree[i];
                }
                return ans;
            }
    }T;
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    int n,m;
    int a[N],b[N];
    void Input()
    {
        R1(n),R1(m);
        G.clear();
        int u,v,w;
        F(i,1,n-1) R1(u),R1(v),R1(w),G.Add2(u,v,w);
        F(i,1,m) R1(a[i]),R1(b[i]);
    }

    int fa[N],deep[N],size[N],dis[N];
    int son[N],val[N]; 
    //val[i]: i和fa[i]之间的边权，就是上面说的，“把边权记录在该边的儿子上”
    //dis[i]: i到根节点的带权距离（就是经过的所有边权的和）
    void DFS1(int u,int f)
    {
        fa[u]=f; 
        deep[u]=(u==f)?0:deep[f]+1;
        dis[u]=(u==f)?0:dis[f]+val[u]; 
        size[u]=1;
        son[u]=-1;int Max=-1;
        Tra(i,u)
        {int v=__v;
            if (v!=f)
            {
                val[v]=G.Label(i);
                DFS1(v,u);
                size[u]+=size[v];
                if (size[v]>Max) {Max=size[v];son[u]=v;}
            }
        }
    }
    int DFSid[N],top[N],Time=0;
    void DFS2(int u,int topu)
    {
        DFSid[u]=++Time;
        top[u]=topu;
        if (son[u]==-1) return;
        DFS2(son[u],topu);
        Tra(i,u)
        {int v=__v;
            if (v!=fa[u] and v!=son[u]) DFS2(v,v);
        }
    }
    int LCA(int u,int v) //树剖求LCA （真的只是个LCA，没别的）
    {
        while(top[u]!=top[v])
        {
            if (deep[top[u]]<deep[top[v]]) swap(u,v);
            u=fa[top[u]]; 
        }
        return deep[u]<deep[v]?u:v;
    }
    int PathLen(int u,int v){return dis[u]+dis[v]-2*dis[LCA(u,v)];} //求链<u,v>的带权长度
    void PathAdd(int u,int v,int w=1)
    {
        while(top[u]!=top[v])
        {
            if (deep[top[u]]<deep[top[v]]) swap(u,v);
            T.RAdd(DFSid[top[u]],DFSid[u],w);
            u=fa[top[u]];
        }
        if (deep[u]>deep[v]) swap(u,v);
        T.RAdd(DFSid[u],DFSid[v],1); //常规树剖操作

        int L=LCA(u,v);
        T.RAdd(DFSid[L],DFSid[L],-1); //把多算的减掉
    }
    int Maxlen;
    bool cxk(int k)
    {
        T.BuildTree(n);
        int cnt=0;
        F(i,1,m) if (PathLen(a[i],b[i])>k) //如果这条边权值过大
        {
            ++cnt;
            PathAdd(a[i],b[i],1);
        }
        
        F(i,1,n) 
        {
            if (T.Query(DFSid[i])==cnt and Maxlen-val[i]<=k) 
            // T.Query(DFSid[i])==cnt表示i和fa[i]这条边被所有的该修正的边覆盖了
            //Maxlen-val[i]<=k表示，我能修正所有该修正的边
            {
                return true; //所以这个时候把(i,fa[i])这条边权值设为0，就满足条件了。
            }
        }
        return false;
    }
    void Soviet()
    {
        DFS1(1,1);
        DFS2(1,1);
        Maxlen=-1; F(i,1,m) Maxlen=max(Maxlen,PathLen(a[i],b[i])); //Maxlen珂以提前求，少掉一个m
        T.BuildTree(n);
        int l=0,r=1e9; //注意：l=0（我一开始就是这样写的，没WA过，但是我猜写l=1会WA几个点）
        while(l<r)
        {
            int mid=(l+r)>>1;
            if (cxk(mid)) r=mid;
            else l=mid+1;
        }
        printf("%lld\n",l);
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
    #undef int //long long 
}
int main(){
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w