题解 P6666 【[清华集训2016] 数据交互】
jun头吉吉
·
·
题解
题意
给定一棵 n 个点的树，m 次操作：
- 添加一条路径 (u_i,v_i)，权值为 w_i
- 撤回一次操作
每一次操作后求出一条路径使得与这条路径有交的路径的权值和最大。
题解
100多通过没有题解非常恐怖。来献个丑。
下面只考虑加路径操作，删路径增加一条相反数即可。
下面记 x\in (u,v) 表示 x 在这条路径上。
首先对于一条路径 (u,v)，我们如果简洁地表示出所有与它有交的路径捏？发现有两种 (a,b) 满足条件：
-
\mathrm{LCA}(a,b)\in (u,v)$ 且 $\mathrm{LCA}(a,b)\ne\mathrm{LCA}(u,v)
-
\mathrm{LCA}(u,v)\in (a,b)
发现所有有交的 (a,b) 在上面这个东西中不重不漏得被数到了一次。换成权值这个显然也是不重不漏的。于是我们可以记 val2_i 表示所有 \mathrm{LCA}(u,v)=i 的权值和，val1_i 表示所有 i\in(u,v) 的 w 的权值和。然后我们可以把一条路径有交的权值和写成非常漂亮的形式：路径上除了 \rm LCA 的 val_2 的和加上 val1_{\mathrm{LCA}}。
然后这个就可以直接做了吧。设 f_u 表示从 u 开始往下走最大的 val_2 和，然后转移 u 的时候就算一个儿子的 f 的最大值 mx 和次大值 cmx，转移就是：
\begin{aligned}
&f_u\leftarrow val2_u+mx\\
&ans\leftarrow val1_u+mx+cmx
\end{aligned}
这个直接做就是 \mathcal O(nm) 了，期望得分 30pts。
然后这个东西可以 \rm DDP 吧。我们把重链上的转移写成矩阵，每一个节点开一个 multiset 记录不是重儿子的 f 值，记 mx 为不是重儿子上的最大的 f，cmx 为不是重儿子的次大值，那么：
\begin{pmatrix}
f_u\\
g_u\\
0\end{pmatrix}
=\begin{pmatrix}
val2_u&-\infty& mx+val2_u\\
mx+val1_i&0&mx+cmx+val1_u\\
-\infty&\infty&0
\end{pmatrix}
\times
\begin{pmatrix}
f_{heavy}\\
g_{heavy}\\
0
\end{pmatrix}
这里的矩阵乘法是对应加起来然后取 \max。
其中 f 的意思和上面相同，g 的意思是这条重链到当前为止的最大权值和。全局开一个 multiset 记录所有重链的最大值。
然后对这个矩阵我们考虑 val1 和 val2 的修改。
然后 $val1$ 的修改需要思考一下，矩阵会区间加一个值就会比较麻烦。但是思考一下也不是很麻烦，因为：
$$
\begin{pmatrix}
a&-\infty&b\\
c&0&d\\
-\infty&\infty&0
\end{pmatrix}\times
\begin{pmatrix}
e&-\infty&f\\
g&0&h\\
-\infty&-\infty&0
\end{pmatrix}
=\begin{pmatrix}
a+e&-\infty&\max(a+f,b)\\
\max(e+c,g)&0&\max(c+f,h,d)\\
-\infty&-\infty&0
\end{pmatrix}
$$
发现区间加就是让 $c,d,g,h$ 全部加一个值，发现乘法之后这两个位置仍然是加这个值。然后就可以打懒标记做了。复杂度 $\mathcal O(\log^2n)$。
实现的时候为了方便可以差分成 $4$ 次做，具体实现可以看代码。
## 代码
```cpp
#include<bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define pb push_back
#define pc putchar
#define chkmx(a,b) (a)=max((a),(b))
#define chkmn(a,b) (a)=min((a),(b))
#define fi first
#define se second
using namespace std;
template<class T>
void read(T&x){x=0;char c=getchar();bool f=0;for(;!isdigit(c);c=getchar())f^=c=='-';for(;isdigit(c);c=getchar())x=x*10+(c-'0');if(f)x=-x;}
template<class T,class ...ARK>void read(T&x,ARK&...ark){read(x);read(ark...);}
template<class T>void write(T x){if(x<0)pc('-'),x=-x;if(x>=10)write(x/10);pc(x%10+'0');}
template<class T,class ...ARK>void write(T x,ARK...ark){write(x);pc(' ');write(ark...);}
template<class ...ARK>void writeln(ARK...ark){write(ark...);pc('\n');}
typedef long long ll;
#define lowbit(x) ((x)&-(x))
#define mid ((l+r)>>1)
#define lc (x<<1)
#define rc (x<<1|1)
const int N=1e5+10;
int n,m;
vector<int>e[N];
int fa[N],dep[N],dfn[N],sz[N],top[N],son[N],cnt,down[N];
void dfs1(int u){
dep[u]=dep[fa[u]]+1;
sz[u]=1;
for(auto v:e[u])if(v!=fa[u]){
fa[v]=u;dfs1(v);sz[u]+=sz[v];
if(sz[v]>sz[son[u]])son[u]=v;
}
}
void dfs2(int u){
dfn[u]=++cnt;
if(!top[u]){top[u]=down[u]=u;while(son[down[u]])down[u]=son[down[u]];}
if(son[u])top[son[u]]=top[u],dfs2(son[u]);
for(auto v:e[u])if(v!=fa[u]&&v!=son[u])dfs2(v);
}
struct mat{
// a -oo b
// c 0 d
//-oo -oo 0
ll a,b,c,d;
mat(ll a=0,ll b=0,ll c=0,ll d=0):a(a),b(b),c(c),d(d){}
friend mat operator*(mat A,mat B){
return mat(
A.a+B.a,
max(A.a+B.b,A.b),
max(A.c+B.a,B.c),
max({A.c+B.b,B.d,A.d})
);
}
};
struct node{
mat mt;ll tag;
}t[N<<2];
void pushtag(int x,ll v){
t[x].tag+=v;
t[x].mt.c+=v;
t[x].mt.d+=v;
}
void pushdown(int x){
if(t[x].tag)
pushtag(lc,t[x].tag),
pushtag(rc,t[x].tag),
t[x].tag=0;
}
void pushup(int x){t[x].mt=t[lc].mt*t[rc].mt;}
void add(int x,int l,int r,int ql,int qr,int v){
if(ql<=l&&r<=qr)return pushtag(x,v);
if(r<ql||qr<l)return;
pushdown(x);
add(lc,l,mid,ql,qr,v);
add(rc,mid+1,r,ql,qr,v);
pushup(x);
}
void mdf(int x,int l,int r,int p,mat v){
if(l==r)return t[x].mt=v,void();
pushdown(x);
if(p<=mid)mdf(lc,l,mid,p,v);
else mdf(rc,mid+1,r,p,v);
pushup(x);
}
mat qry(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return t[x].mt;
pushdown(x);
if(qr<=mid)return qry(lc,l,mid,ql,qr);
if(mid<ql)return qry(rc,mid+1,r,ql,qr);
return qry(lc,l,mid,ql,qr)*qry(rc,mid+1,r,ql,qr);
}
ll get(int x,int l,int r,int p){
if(l==r)return t[x].tag;
pushdown(x);
if(p<=mid)return get(lc,l,mid,p);
else return get(rc,mid+1,r,p);
}
ll val2[N];
multiset<ll>fl[N],res;
mat getmat(int u){
ll v1=get(1,1,n,dfn[u]);
ll v2=val2[u];
ll mx=*fl[u].rbegin(),cmx=*++fl[u].rbegin();
return mat(v2,mx+v2,mx+v1,mx+cmx+v1);
}
int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
u=fa[top[u]];
}
if(dep[u]>dep[v])return v;
return u;
}
void addv1(int u,int w){
//从 u 到 根的路径 加 w
int x=u;
while(x){
mat ori=qry(1,1,n,dfn[top[x]],dfn[down[top[x]]]);
ll f=max(ori.a,ori.b),g=max(ori.c,ori.d);
res.erase(res.find(g));
if(fa[top[x]])fl[fa[top[x]]].erase(fl[fa[top[x]]].find(f));
x=fa[top[x]];
}
x=u;
while(x){
add(1,1,n,dfn[top[x]],dfn[x],w);
mat now=qry(1,1,n,dfn[top[x]],dfn[down[top[x]]]);
ll f=max(now.a,now.b),g=max(now.c,now.d);
res.insert(g);
if(fa[top[x]]){
fl[fa[top[x]]].insert(f);
mdf(1,1,n,dfn[fa[top[x]]],getmat(fa[top[x]]));
}
x=fa[top[x]];
}
}
void addv2(int u,int w){
//给 u 的 v2 加上 w
int x=u;
while(x){
mat ori=qry(1,1,n,dfn[top[x]],dfn[down[top[x]]]);
ll f=max(ori.a,ori.b),g=max(ori.c,ori.d);
res.erase(res.find(g));
if(fa[top[x]])
fl[fa[top[x]]].erase(fl[fa[top[x]]].find(f));
x=fa[top[x]];
}
val2[u]+=w;
mdf(1,1,n,dfn[u],getmat(u));
x=u;
while(x){
mat now=qry(1,1,n,dfn[top[x]],dfn[down[top[x]]]);
ll f=max(now.a,now.b),g=max(now.c,now.d);
res.insert(g);
if(fa[top[x]]){
fl[fa[top[x]]].insert(f);
mdf(1,1,n,dfn[fa[top[x]]],getmat(fa[top[x]]));
}
x=fa[top[x]];
}
}
void add(int u,int v,int w){
int l=lca(u,v);
addv1(u,w);addv1(v,w);addv1(l,-w);addv1(fa[l],-w);
addv2(l,w);
}
int x[N],y[N],w[N];
signed main(){
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
read(n,m);
for(int i=1,u,v;i<n;i++)read(u,v),e[u].pb(v),e[v].pb(u);
dfs1(1);dfs2(1);
for(int i=1;i<=n;i++)fl[i].insert(0),fl[i].insert(0);
for(int i=1;i<=n;i++)for(auto j:e[i])if(j!=son[i]&&j!=fa[i])fl[i].insert(0);
for(int i=1;i<=n;i++)if(i==top[i])res.insert(0);
for(int i=1;i<=m;i++){
char op=getchar();while(op!='+'&&op!='-')op=getchar();
if(op=='+'){
read(x[i],y[i],w[i]);
add(x[i],y[i],w[i]);
}else{
int t;read(t);
add(x[t],y[t],-w[t]);
}
//for(int i=1;i<=n;i++)write(get(1,1,n,dfn[i])),pc(' ');pc('\n');
writeln(*res.rbegin());
}
}
```