物流运输

Source

jisuanke

Hint

请先思考后再展开

方向一:无脑cdq是log方的,考虑怎么降低
方向二:路径两端-A,lca+2A,求子树和

Solution

请先思考后再展开

首先求路径的次大值肯定是倍增的了,nlogn,这没什么好说的
第二部分想了很久,除了cdq啥也没想到,只好开写,写的过程中感觉很接近log,但就是有个二分不知道怎么优化
先给出双log的代码,都是cdq的基本操作了

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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
using namespace std;
namespace mine
{
typedef long long ll;
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
#define PB push_back
#define vc vector
void chmax(int &x,const ll y) {x=(x>y?x:y);}
void chmin(int &x,const ll y) {x=(x<y?x:y);}
ll qread()
{
ll ans=0,f=1;char c=getchar();
while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) putchar('-'),num=-num;
if(num>=10) write(num/10);
putchar('0'+num%10);
}
void write1(ll num){write(num);putchar(' ');}
void write2(ll num){write(num);putchar('\n');}
const int INF=0x3f3f3f3f;
const int MOD=19930726;
void add(ll &a,ll b){a+=b;if(a>=MOD)a-=MOD;if(a<=-MOD)a+=MOD;}
ll qpower(ll x,int e)
{
ll ans=1;
while(e)
{
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
ll invm(ll x){return qpower(x,MOD-2);}
const int N=1e5+10,M=5e5+10;

ll sum[N];
struct Data
{
int fl,fr;
int ll,rr;
int op,id;//0边,id表示边的编号
};
bool cmp(Data x,Data y){return x.fl<y.fl;}
bool cmp1(Data x,Data y)
{
if(x.ll!=y.ll) return x.ll<y.ll;
return x.op<y.op;
}
bool cmp2(Data x,Data y)
{
if(x.rr!=y.rr) return x.rr>y.rr;
return x.op<y.op;
}

ll ss[M*4];
struct CDQ
{
vc<Data> qq;
void cdq(int l,int r)
{
if(l>=r) return;
int mid=(l+r)>>1;
cdq(l,mid);sort(qq.begin()+l,qq.begin()+mid+1,cmp);
cdq(mid+1,r);sort(qq.begin()+mid+1,qq.begin()+r+1,cmp);
ss[l-1]=0;for(int i=l;i<=mid;i++) ss[i]=ss[i-1]+qq[i].op;
for(int i=mid+1;i<=r;i++) if(qq[i].id>0)
{
int x=lower_bound(qq.begin()+l,qq.begin()+mid+1,qq[i],cmp)-qq.begin();
int y=upper_bound(qq.begin()+l,qq.begin()+mid+1,(Data){qq[i].fr,0,0,0,0,0},cmp)-qq.begin()-1;
if(x<=y) sum[qq[i].id]+=ss[y]-ss[x-1];
}
}
void solve()
{
int n=qq.size();
sort(qq.begin(),qq.end(),cmp1);cdq(0,n-1);
sort(qq.begin(),qq.end(),cmp2);cdq(0,n-1);
}
}cdq[M*2];


int bin[30];int f[N][30];pr up[N][30];
pr merg(pr a,pr b)
{
if(a.FR!=b.FR)
{
if(a.FR>b.FR) return MP(a.FR,max(a.SE,b.FR));
return MP(b.FR,max(b.SE,a.FR));
}
else return MP(a.FR,max(a.SE,b.SE));
}
vc<pr> son[N];int dep[N],dfn[N],id=0,siz[N];
void pre(int x,int fa)
{
dep[x]=dep[fa]+1;dfn[x]=++id;siz[x]=1;
f[x][0]=fa;for(int i=1;i<=20;i++) {f[x][i]=f[f[x][i-1]][i-1],up[x][i]=merg(up[x][i-1],up[f[x][i-1]][i-1]);/*if(f[x][i])printf("f(%d,%d)=%d\n",x,i,f[x][i]);*/}
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t].FR,c=son[x][t].SE;if(y==fa)continue;
up[y][0]=MP(c,0);pre(y,x);siz[x]+=siz[y];

cdq[c].qq.PB((Data){dfn[y],dfn[y]+siz[y]-1,dfn[y],dfn[y]+siz[y]-1,0,y});
}
}
pr ask(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
pr now=MP(0,0);for(int i=20;i>=0;i--) if(bin[i]<=dep[x]-dep[y]) now=merg(now,up[x][i]),x=f[x][i];
if(x==y) return now;
for(int i=20;i>=0;i--) if(f[x][i]!=f[y][i]) now=merg(now,merg(up[x][i],up[y][i])),x=f[x][i],y=f[y][i];
return merg(now,merg(up[x][0],up[y][0]));
}

void main()
{
int n=qread(),m=qread();
for(int i=1;i<n;i++) {int x=qread(),y=qread(),c=qread();son[x].PB(MP(y,c));son[y].PB(MP(x,c));}
bin[0]=1;for(int i=1;i<=20;i++) bin[i]=bin[i-1]<<1;
pre(1,0);
ll ans=0;
for(int i=1;i<=m;i++)
{
int x=qread(),y=qread();pr now=ask(x,y);ans+=now.FR;
cdq[now.FR].qq.PB((Data){dfn[x],dfn[x],dfn[y],dfn[y],now.FR-now.SE,0});
cdq[now.FR].qq.PB((Data){dfn[y],dfn[y],dfn[x],dfn[x],now.FR-now.SE,0});
}
for(int i=0;i<M*2;i++) cdq[i].solve();
ll mx=0;for(int i=1;i<=n;i++) mx=max(mx,sum[i]);
write(ans-mx);
}
};
int main()
{
freopen("a.in","r",stdin);
srand(time(0));
mine::main();
}

这个二分说大也不大,说小也不小,感觉很能优化但又不太会……后来仔细一想,发现前缀和那句是可以拆开来的
就是说跑两次cdq分别计算,这样就是单log的了,然后顺便修了点bug(越界问题)
复杂度虽然是对的,但常数略大,开o2是1s,不开就要5s,主要是stl用的有点多……(重度依赖症

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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
using namespace std;
namespace mine
{
typedef long long ll;
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
#define PB push_back
#define vc vector
void chmax(int &x,const ll y) {x=(x>y?x:y);}
void chmin(int &x,const ll y) {x=(x<y?x:y);}
ll qread()
{
ll ans=0,f=1;char c=getchar();
while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) putchar('-'),num=-num;
if(num>=10) write(num/10);
putchar('0'+num%10);
}
void write1(ll num){write(num);putchar(' ');}
void write2(ll num){write(num);putchar('\n');}
const int INF=0x3f3f3f3f;
const int MOD=19930726;
void add(ll &a,ll b){a+=b;if(a>=MOD)a-=MOD;if(a<=-MOD)a+=MOD;}
ll qpower(ll x,int e)
{
ll ans=1;
while(e)
{
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
ll invm(ll x){return qpower(x,MOD-2);}
const int N=1e5+10,M=5e5+10;

ll sum[N];
struct Data
{
int fl,fr;
int ll,rr;
int op,id;//0边,id表示边的编号
};
bool cmp1(Data x,Data y)
{
if(x.ll!=y.ll) return x.ll<y.ll;
return x.op<y.op;
}
bool cmp2(Data x,Data y)
{
if(x.rr!=y.rr) return x.rr>y.rr;
return x.op<y.op;
}

ll ss[M*4];
Data tmp[M*4];
struct CDQ
{
vc<Data> qq;
bool cmp(Data a,Data b,int op) {return ((op<0 and !a.op)?a.fr:a.fl)<((op<0 and !b.op)?b.fr:b.fl);}
void cdq(int op,int l,int r)
{
if(l>=r) return;
int mid=(l+r)>>1;cdq(op,l,mid);cdq(op,mid+1,r);
ss[l-1]=0;for(int i=l;i<=mid;i++) ss[i]=ss[i-1]+qq[i].op;

if(op>0)//左端点
{
int now=l;
for(int i=mid+1;i<=r;i++) if(qq[i].id>0)
{
while(now<=mid and qq[now].fl<qq[i].fl) now++;
sum[qq[i].id]-=ss[now-1];
}
}
else
{
int now=l-1;
for(int i=mid+1;i<=r;i++) if(qq[i].id>0)
{
while(now+1<=mid and qq[now+1].fl<=qq[i].fr) now++;
sum[qq[i].id]+=ss[now];
}
}
int now=l,xx=l,yy=mid+1;
while(xx<=mid and yy<=r) tmp[now++]=(cmp(qq[xx],qq[yy],op)?qq[xx++]:qq[yy++]);
while(xx<=mid) tmp[now++]=qq[xx++];while(yy<=r) tmp[now++]=qq[yy++];
for(int i=l;i<=r;i++) qq[i]=tmp[i];
}
void solve()
{
int n=qq.size();if(n==1) return;
sort(qq.begin()+1,qq.end(),cmp1);cdq(1,1,n-1);
sort(qq.begin()+1,qq.end(),cmp1);cdq(-1,1,n-1);
sort(qq.begin()+1,qq.end(),cmp2);cdq(1,1,n-1);
sort(qq.begin()+1,qq.end(),cmp2);cdq(-1,1,n-1);
}
}cdq[M*2];


int bin[30];int f[N][30];pr up[N][30];
pr merg(pr a,pr b)
{
if(a.FR!=b.FR)
{
if(a.FR>b.FR) return MP(a.FR,max(a.SE,b.FR));
return MP(b.FR,max(b.SE,a.FR));
}
else return MP(a.FR,max(a.SE,b.SE));
}
vc<pr> son[N];int dep[N],dfn[N],id=0,siz[N];
void pre(int x,int fa)
{
dep[x]=dep[fa]+1;dfn[x]=++id;siz[x]=1;
f[x][0]=fa;for(int i=1;i<=20;i++) f[x][i]=f[f[x][i-1]][i-1],up[x][i]=merg(up[x][i-1],up[f[x][i-1]][i-1]);
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t].FR,c=son[x][t].SE;if(y==fa)continue;
up[y][0]=MP(c,0);pre(y,x);siz[x]+=siz[y];
cdq[c].qq.PB((Data){dfn[y],dfn[y]+siz[y]-1,dfn[y],dfn[y]+siz[y]-1,0,y});
}
}
pr ask(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
pr now=MP(0,0);for(int i=20;i>=0;i--) if(bin[i]<=dep[x]-dep[y]) now=merg(now,up[x][i]),x=f[x][i];
if(x==y) return now;
for(int i=20;i>=0;i--) if(f[x][i]!=f[y][i]) now=merg(now,merg(up[x][i],up[y][i])),x=f[x][i],y=f[y][i];
return merg(now,merg(up[x][0],up[y][0]));
}

void main()
{
for(int i=0;i<M*2;i++) cdq[i].qq.PB((Data){0,0,0,0,0,0});//debug

int n=qread(),m=qread();
for(int i=1;i<n;i++) {int x=qread(),y=qread(),c=qread();son[x].PB(MP(y,c));son[y].PB(MP(x,c));}
bin[0]=1;for(int i=1;i<=20;i++) bin[i]=bin[i-1]<<1;
pre(1,0);
ll ans=0;
for(int i=1;i<=m;i++)
{
int x=qread(),y=qread();pr now=ask(x,y);ans+=now.FR;
cdq[now.FR].qq.PB((Data){dfn[x],dfn[x],dfn[y],dfn[y],now.FR-now.SE,0});
cdq[now.FR].qq.PB((Data){dfn[y],dfn[y],dfn[x],dfn[x],now.FR-now.SE,0});
}
for(int i=0;i<M*2;i++) cdq[i].solve();
ll mx=0;for(int i=1;i<=n;i++) mx=max(mx,sum[i]);
write(ans-mx);
}
};
int main()
{
freopen("a.in","r",stdin);
srand(time(0));
mine::main();
}

方向一的写法可能大家会嫌麻烦……不过确实没想到更好的

方向二就好写很多了
一种思路是半夜睡不着想到的,首先点代表到父亲的那条边,用点建c棵虚树,然后每条路径上去打标记最后推一推
那么我们就是要找到一个点在虚树上最近的点,然后我猜了个结论,就是把虚树上的点按照欧拉序排序,然后把这个点的欧拉序用来询问左右两侧第一个点,答案就是其中一个(假如这个结论是假的麻烦在下面评论……但感觉挺对的
那么复杂度就是 O(mlogn)

然后其实用下标区间为1到c的动态开点权值线段树合并也是可以的
据说空间略大,不过应该也挺好写的,都是比较常规的操作

最后就是题解的最简洁做法了,按颜色离线,然后就可以用树状数组代替线段树了,空间为n,时间依然是mlogn
没看懂可以看代码,非常好懂
以下给出的是std的(不是我)的代码

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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<bitset>
#include<ctime>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pii pair<int,int>
using namespace std;
inline char nc() {
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(void) {
char ch=nc();
int sum=0;
while(!(ch>='0'&&ch<='9'))
ch=nc();
while(ch>='0'&&ch<='9')
sum=(sum<<3)+(sum<<1)+(ch^48),ch=nc();
return sum;
}
int wsta[20],wtp;
inline void write(LL x)
{
if(x<0)putchar('-'),x=-x;
if(x==0){putchar('0');return ;}
wtp=0;
while(x)wsta[++wtp]=x%10,x/=10;
while(wtp)putchar(wsta[wtp--]+'0');
}
inline void pr1(int x){write(x);putchar(' ');}
inline void pr2(LL x){write(x);putchar('\n');}
const int MAXN=100005;
const int MAXM=500005;
const int MAXC=1000005;
struct edge{int x,y,c,next;}a[2*MAXN];int len,last[MAXN];
void ins(int x,int y,int c){len++;a[len].x=x;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;}

struct node
{
int first,second;
node(){}
node(int _first,int _second){first=_first;second=_second;}
};
int in[MAXN],ot[MAXN],id,dep[MAXN];
int fa[18][MAXN],cal[2][18][MAXN],bin[25];
int mx[3],g[5];
inline node merge(int u1,int u2,int u3,int u4)
{
g[1]=u1;g[2]=u2;g[3]=u3;g[4]=u4;
sort(g+1,g+1+4);
int nw=3;
while(g[nw]==g[nw+1])nw--;
return node(g[4],g[nw]);
}
void dfs(int x)
{
in[x]=++id;
for(int i=1;bin[i]<=dep[x];i++)
{
fa[i][x]=fa[i-1][fa[i-1][x]];
node u=merge(cal[0][i-1][x],cal[1][i-1][x],cal[0][i-1][fa[i-1][x]],cal[1][i-1][fa[i-1][x]]);
cal[0][i][x]=u.first;cal[1][i][x]=u.second;
}
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(y!=fa[0][x])
{
fa[0][y]=x;
dep[y]=dep[x]+1;
cal[0][0][y]=a[k].c;
dfs(y);
}
}
ot[x]=id;
}
int Lg[MAXN];
inline int lca(int x,int y)
{
mx[1]=mx[2]=0;
if(dep[x]<dep[y])swap(x,y);
for(int i=Lg[dep[x]];i>=0;i--)if(bin[i]<=dep[x]&&dep[fa[i][x]]>=dep[y])
{
node u=merge(mx[1],mx[2],cal[0][i][x],cal[1][i][x]);
mx[1]=u.first;mx[2]=u.second;
x=fa[i][x];
}
if(x==y)return x;
for(int i=Lg[dep[x]];i>=0;i--)if(bin[i]<=dep[x]&&fa[i][x]!=fa[i][y])
{
node u=merge(cal[0][i][x],cal[1][i][x],cal[0][i][y],cal[1][i][y]);
node v=merge(mx[1],mx[2],u.first,u.second);
mx[1]=v.first;mx[2]=v.second;
x=fa[i][x],y=fa[i][y];
}
node u=merge(cal[0][0][x],cal[0][0][y],mx[1],mx[2]);
mx[1]=u.first;mx[2]=u.second;
return fa[0][x];
}
int n,m,L;
struct EDGE{int x,y,c;}E[MAXN];
bool cmp(EDGE n1,EDGE n2){return n1.c<n2.c;}
LL S[MAXN];
int lowbit(int x){return x&-x;}
void modify(int x,int c){for(;x<=n;x+=lowbit(x))S[x]+=c;}
LL qry(int x){LL ret=0;for(;x>=1;x-=lowbit(x))ret+=S[x];return ret;}
vector<pii> vec[MAXC];

int main()
{
freopen("gcakioi10.in","r",stdin);
freopen("gcakioi10.out","w",stdout);
for(int i=2;i<MAXN;i++)Lg[i]=Lg[i>>1]+1;
bin[0]=1;for(int i=1;i<=20;i++)bin[i]=bin[i-1]<<1;
n=read();m=read();
for(int i=1;i<n;i++)
{
int x=read(),y=read(),c=read();
E[i].x=x;E[i].y=y;E[i].c=c;
ins(x,y,c);ins(y,x,c);
}
dfs(1);
LL sum=0;
for(int i=1;i<=m;i++)
{
int S=read(),T=read();
int LA=lca(S,T);
sum+=mx[1];int lst=mx[1]-mx[2];
vec[mx[1]].push_back(mp(in[S],lst));
vec[mx[1]].push_back(mp(in[T],lst));
vec[mx[1]].push_back(mp(in[LA],-2*lst));
}
LL ans=(1LL<<63-1);
sort(E+1,E+n,cmp);
for(int ls=0,i=1;i<n;i++)
{
if(E[i].c!=ls)
{
for(int j=0;j<vec[ls].size();j++)modify(vec[ls][j].first,-vec[ls][j].second);
ls=E[i].c;
for(int j=0;j<vec[ls].size();j++)modify(vec[ls][j].first,vec[ls][j].second);
}
int x=E[i].x,y=E[i].y;
if(dep[x]<dep[y])swap(x,y);
LL del=qry(ot[x])-qry(in[x]-1);
ans=min(ans,sum-del);
}
pr2(ans);
return 0;
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/eb00.html
转载请注明出处,谢谢!