Reincarnation

正因为梦易碎，才格外美好。

Contest20230409

发表于 更新于 分类于
本文字数： 9.5k 阅读时长 ≈ 9 分钟

不可做级别。

原题面一览



签到题

比较典但是毒瘤的换根。

考虑 怎么做，设 表示以 为根的子树贡献，这是显然的，我们考虑为 的子结点钦定一个顺序，记为 ，以及子树大小 和子树权值和 ，取一个子树前缀和记为 ，转移方程如下：

那么我们按照 从小往大转移即可，时间复杂度 。

考虑怎么换根，记录反向的贡献（除开 的子树的贡献），然后将其视为 的子树然后再次排序进行转移，贡献多少在换根的时候就退出多少，思路好像很简单，但我说不太明白，但转移的细节确实比较多，调了一上午。

参考实现
 
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
#include<bits/stdc++.h>
#define re register
typedef long long ll;
typedef double ld;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=getchar(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
// using ll=__int128_t;
const int MAXN=2e5+10;
const ll INF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-8;
int N;
ll Val[MAXN],Dp[MAXN],Sum[MAXN],ans=INF;
ll Suf[MAXN],Pre[MAXN],Pref[MAXN],Suff[MAXN],Siz[MAXN];
ll Son[MAXN];
std::vector<int>Edges[MAXN];
inline bool cmp(int a,int b)
{ return Sum[a]*Siz[b]>Sum[b]*Siz[a]; }
void dfsPre(int x,int last)
{
    Sum[x]=Val[x],Siz[x]=1;
    for(auto v:Edges[x])
    {
        if(v==last) continue;
        dfsPre(v,x);
        Siz[x]+=Siz[v],Sum[x]+=Sum[v];
    }
}
void dfsTree(int x,int last)
{
    Dp[x]=Val[x];
    std::sort(Edges[x].begin(),Edges[x].end(),cmp);
    int siz=1;
    for(auto v:Edges[x])
    {
    	if(v==last) continue;
        dfsTree(v,x);
        Dp[x]+=Dp[v]+Sum[v]*siz;
        siz+=Siz[v];
    }
}
ll Sums,res[MAXN];
void dfsCalc(int x,int last)
{
	int pos=0,pre=1;
	int lasts=Siz[last],lastm=Sum[last];
	Siz[last]=N-Siz[x],Sum[last]=Sums-Sum[x];
	std::sort(Edges[x].begin(),Edges[x].end(),cmp);
    res[x]=Val[x],Pre[0]=Val[x];
    for(auto v:Edges[x])
    {
    	++pos;
    	if(v==last) res[x]+=Son[x]+Sum[v]*pre;
    	else res[x]+=Dp[v]+Sum[v]*pre;
    	pre+=Siz[v];
    	Pre[pos]=Pre[pos-1]+Sum[v];
    }
    checkMin(ans,res[x]);
    pos=0;pre=1;
    Siz[last]=lasts,Sum[last]=lastm;
    for(auto v:Edges[x])
    {
    	++pos;
    	if(v==last) pre+=N-Siz[x];
    	else Son[v]=res[x]-Dp[v]-Sum[v]*pre-(Sums-Pre[pos])*Siz[v],pre+=Siz[v];
    }
    for(auto v:Edges[x]) if(v!=last) dfsCalc(v,x);
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N);
    for(int i=2,u,v;i<=N;++i) read(u,v),Edges[u].emplace_back(v),Edges[v].emplace_back(u);
    for(int i=1;i<=N;++i) read(Val[i]);
    dfsPre(1,0);Sums=1[Sum];
	dfsTree(1,0),dfsCalc(1,0);
    // for(int i=1;i<=N;++i) write(i[res],' ');
    write(ans);
    return 0;
}
/*
 
*/

简单题

考虑把最开始的最小生成树给找到，然后替换边。每一次会添加一条边，然后形成一个环，同样的，对于我们添加的这一条边，能够影响的也只有当前这一个环。

对于树边（从一开始就存在在最小生成树里的边），如果其不是所构成环上的除开其它树边的最小边了，就会被另外一条非树边所代替；对于非树边，如果这条边比环上所有树边的权值都要大了，就不可能成为生成树的边。

所以考虑树剖维护边权，对于树边，在边上赋上权值后让非树边去查询，得到非树边答案，对于非树边，在路径上进行 checkMin 操作，然后让树边去查询即可。

参考实现
 
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
198
199
200
201
202
203

#include<bits/stdc++.h>
#define re register
typedef long long ll;
typedef long double ld;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=getchar(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    if(t) x=-x;
}
template<class T,class ...Arc>
inline void read(T &x,Arc &...arc){ read(x),read(arc...); }
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...Arc>
inline void write(T x,Arc ...arc){ write(x),write(arc...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
template<class T>
inline T abs(T x){ return x>0?x:-x; }
const int MAXN=1e6+10;
const ll INF=1ll<<60;
struct Node
{ int x,y,id;ll val; }Ed[MAXN];
struct G
{ int next,to;ll val; }Edge[MAXN<<1];
int Head[MAXN],Total;
bool Vis[MAXN];
int N,M,Cnt,Pos[MAXN];
ll ans[MAXN];
int Rt[MAXN],Dep[MAXN],Fa[MAXN],Dfn[MAXN],Top[MAXN],Son[MAXN],Siz[MAXN];
inline void addEdge(int u,int v,ll w)
{
    Edge[++Total]=(G){Head[u],v,w};Head[u]=Total;
    Edge[++Total]=(G){Head[v],u,w};Head[v]=Total;
}
void dfsTree(int x,int last)
{
    Fa[x]=last,Dep[x]=Dep[last]+1,Siz[x]=1;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfsTree(v,x);
        Siz[x]+=Siz[v];
        if(!Son[x]||Siz[v]>Siz[Son[x]]) Son[x]=v;
    }
}
void dfsChain(int x,int topf)
{
    Top[x]=topf,Dfn[x]=++Cnt;
    if(!Son[x]) return ;
    dfsChain(Son[x],topf);
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==Fa[x]||v==Son[x]) continue;
        dfsChain(v,v);
    }
}
inline bool cmp(const Node &x,const Node &y){ return x.val<y.val; }
inline int getRt(int x)
{ return Rt[x]==x?x:Rt[x]=getRt(Rt[x]); }
#define ls (p<<1)
#define rs (p<<1|1)
struct Seg
{
    int l,r;
    ll val,tag,mx,sec;
}Tr[MAXN<<2];
inline void pushUp(int p)
{
    if(Tr[ls].mx==INF&&Tr[rs].mx==INF)
    {
        Tr[p].mx=INF,Tr[p].sec=-INF;
        return ;
    }
    if(checkMax(Tr[p].mx,Tr[ls].mx)) Tr[p].sec=std::max(Tr[ls].sec,Tr[rs].mx);
    if(checkMax(Tr[p].mx,Tr[rs].mx)) Tr[p].sec=std::max(Tr[rs].sec,Tr[ls].mx);
}
inline void pushDown(int p)
{
    if(Tr[p].tag==INF) return ;
    if(checkMin(Tr[ls].mx,Tr[p].tag)) checkMin(Tr[ls].tag,Tr[p].tag);
    if(checkMin(Tr[rs].mx,Tr[p].tag)) checkMin(Tr[rs].tag,Tr[p].tag);
    Tr[p].tag=INF;
    return ;
}
void build(int p,int l,int r)
{
    Tr[p].l=l,Tr[p].r=r,Tr[p].tag=Tr[p].mx=INF;
    Tr[p].sec=-INF;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
}
void modifyX(int p,int x,ll v)
{
    if(Tr[p].l==Tr[p].r) return Tr[p].val+=v,void();
    int mid=(Tr[p].l+Tr[p].r)>>1;
    x<=mid?modifyX(ls,x,v):modifyX(rs,x,v);
    Tr[p].val=std::max(Tr[ls].val,Tr[rs].val);
}
ll queryMax(int p,int l,int r)
{
    if(Tr[p].l==l&&Tr[p].r==r) return Tr[p].val;
    int mid=(Tr[p].l+Tr[p].r)>>1;
    if(r<=mid) return queryMax(ls,l,r);
    else if(l>mid) return queryMax(rs,l,r);
    else return std::max(queryMax(ls,l,mid),queryMax(rs,mid+1,r));
}
void modifyMin(int p,int l,int r,ll v)
{
    if(Tr[p].mx<=v) return ;
    if(l<=Tr[p].l&&Tr[p].r<=r)
        if(Tr[p].sec<=v)
        {
            Tr[p].mx=v,checkMin(Tr[p].tag,v);
            return ;
        }
    pushDown(p);
    int mid=(Tr[p].l+Tr[p].r)>>1;
    if(l<=mid) modifyMin(ls,l,std::min(r,mid),v);
    if(mid<r) modifyMin(rs,std::max(l,mid+1),r,v);
    pushUp(p);
}
ll querySec(int p,int x)
{
    if(Tr[p].l==Tr[p].r) return Tr[p].mx;
    pushDown(p);
    int mid=(Tr[p].l+Tr[p].r)>>1;
    return x<=mid?querySec(ls,x):querySec(rs,x);
}
inline ll Path(int x,int y,ll v)
{
    if(!x||!y) return 0;
    ll res=0;
    while(Top[x]!=Top[y])
    {
        if(Dep[Top[x]]<Dep[Top[y]]) std::swap(x,y);
        checkMax(res,queryMax(1,Dfn[Top[x]],Dfn[x]));
        modifyMin(1,Dfn[Top[x]],Dfn[x],v);
        x=Fa[Top[x]];
    }
    if(Dep[x]>Dep[y]) std::swap(x,y);
    if(x==y) return res;
    checkMax(res,queryMax(1,Dfn[Son[x]],Dfn[y]));
    modifyMin(1,Dfn[Son[x]],Dfn[y],v);
    return res;
}
int main()
{
    // freopen("easy.in","r",stdin);
    // freopen("easy.out","w",stdout);
    read(N,M);
    for(int i=1;i<=M;++i) read(Ed[i].x,Ed[i].y,Ed[i].val),Ed[i].id=i;
    std::sort(Ed+1,Ed+M+1,cmp);
    for(int i=1;i<=N;++i) Rt[i]=i;
    int res=0;
    for(int i=1;i<=M;++i)
    {
        int p=getRt(Ed[i].x),q=getRt(Ed[i].y);
        if(p!=q)
        {
            Rt[q]=p;
            Vis[i]=1;++res;
            addEdge(Ed[i].x,Ed[i].y,Ed[i].val);
        }
        if(res==N-1) break;
    }
    dfsTree(1,0),dfsChain(1,1);
    build(1,1,N);
    for(int i=1;i<=M;++i) if(Vis[i])
    {
        if(Fa[Ed[i].x]==Ed[i].y) modifyX(1,Dfn[Ed[i].x],Ed[i].val),Pos[i]=Ed[i].x;
        else modifyX(1,Dfn[Ed[i].y],Ed[i].val),Pos[i]=Ed[i].y;
    }
    for(int i=1;i<=M;++i) if(!Vis[i]) ans[Ed[i].id]=Path(Ed[i].x,Ed[i].y,Ed[i].val);
    for(int i=1;i<=M;++i) if(Vis[i]) ans[Ed[i].id]=querySec(1,Dfn[Pos[i]]);
    for(int i=1;i<=M;++i) write(std::min(ans[i],(ll)1e9),'\n');
    return 0;
}
/*
 
*/

这个是 的写法，好像有一支 的，排序后用并查集维护，不太好想。

不难题

相关文章