Question link
Click to open link
Question solution
Consider how to calculate
f
(
U
)
f(U)
f(U), I don’t know how to think of the following solution
One trick is to hang the path in
l
c
a
lca
lca on
we order
f
u
f_{u}
fu? means completely included in
u
u
the largest independent set of paths in the subtree of u
Consider transferring, remember
s
u
m
u
=
∑
v
∈
s
o
n
(
u
)
f
v
sum_{u}=\sum\limits_{v\in son(u)}f_v
sumu?=v∈son(u)∑?fv?
- if
u
u
u is not on any of the selected paths
f
u
=
s
u
m
u
f_u=sum_u
fu?=sumu?
-
u
u
The weight value of u is
w
w
path of w
x
→
y
x\to y
x→y up
Consider forx
→
u
x\to u
x→u and
y
→
u
y\to u
The paths of y→u are considered separately, and the formula is given first:
f
u
=
s
u
m
u
+
w
?
∑
q
∈
p
a
t
h
(
x
,
u
)
or
q
∈
p
a
t
h
(
y
,
u
)
(
f
q
?
s
u
m
q
)
f_u=sum_u + w-\sum\limits_{q\in path(x,u)\;or\;q\in path(y,u)}(f_q-sum_q)
fu?=sumu? + w?q∈path(x,u) or q∈path(y,u)∑?(fqsumq?)
need to subtractf
q
?
s
u
m
q
f_q-sum_q
fqsumq? because
p
a
t
h
(
x
,
y
)
path(x,y)
No point on path(x,y) can be selected on other paths, and our state naturally fits
f
q
?
s
u
m
q
f_q-sum_q
fqsumq? Yes
q
q
q is not here
q
q
q Number of solutions on the subtree path
The above things can be used
B
I
T
BIT
BIT maintenance, specifically, it needs to implement single point addition and chain search, and because of the unique structure of the traversal tree, we can turn it into subtree addition and single point search
At the same time we need another array
g
u
g_u
gu? means
u
u
u The largest independent set of paths outside the subtree
Continuing to consider classification transfer, we consider using
g
u
g_u
Derivation of the answer for gu?
g
v
(
v
∈
s
o
n
(
u
)
)
g_v(v\in son(u))
The answer for gv?(v∈son(u))
-
u
u
u is not on any path
g
v
=
g
u
+
s
u
m
u
?
f
v
g_v=g_u + sum_u-f_v
gv?=gu? + sumufv?
-
u
u
The weight value of u is
w
w
path of w
x
→
y
x\to y
on x→y,
x
→
y
x\to y
x→y does not pass
v
v
v
makex
,
y
x,y
x,y
l
c
a
lca
lca is
h
h
h
It is not difficult to come up with this formula:g
v
=
g
h
+
w
+
s
u
m
h
?
∑
q
∈
p
a
t
h
(
x
,
y
)
(
f
q
?
s
u
m
q
)
?
f
v
g_v=g_h + w + sum_h-\sum\limits_{q\in path(x,y)}(f_q-sum_q)-f_v
gv?=gh? + w + sumhq∈path(x,y)∑?(fqsumq?)?fv?
The things above can flatten the tree into
d
f
s
dfs
dfs order, and then do the line segment tree, pay attention to special considerations
l
c
a
=
u
lca=u
lca=u case
Finally, you can consider calculating the answer
I marked the violent calculation with comments in the program, and then optimized the violent calculation. This is not too difficult, just pay attention to some details.
time complexity
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
#include <bits/stdc + + .h>
#define int long long
#define lowbit(x) x & amp;-x
#define pb push_back
using namespace std;
const int N=300100,P=998244353;
struct Lines{<!-- --> int u,v,w;};
int n,m,ans;
int depth[N],up[N][20],siz[N];
int Ldfn[N],Rdfn[N],dfs_clock;
int f[N],sum[N];//f[u]: The sum of the weights of disjoint paths in the u subtree
int g[N];//g[u]: The sum of the weights of non-intersecting paths outside the u subtree
int e[N<<1],ne[N<<1],h[N],idx;
vector<int> G[N];
vector<Lines> ln[N];
inline int read(){<!-- -->
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1) + (FF<<3) + ch-48;
return FF*RR;
}
void predfs(int u,int fa){<!-- -->
depth[u]=depth[fa] + 1;
Ldfn[u]= + + dfs_clock,up[u][0]=fa;
for(int i=h[u];~i;i=ne[i]) if(e[i]!=fa) G[u].pb(e[i]),predfs(e[i], u);
Rdfn[u]=dfs_clock;
}
int get_lca(int x,int y){<!-- -->
if(depth[x]>depth[y]) swap(x,y);
for(int i=18;i>=0;i--) if(depth[up[y][i]]>=depth[x]) y=up[y][i];
if(x==y) return x;
for(int i=18;i>=0;i--) if(up[x][i]!=up[y][i]) x=up[x][i],y=up[y ][i];
return up[x][0];
}
struct BIT{<!-- -->
int tr[N];
void inc(int x,int v){<!-- --> for(;x<=n;x + =lowbit(x)) tr[x] + =v;}
void add(int l,int r,int v){<!-- --> inc(l,v),inc(r + 1,-v);}
int ask(int x){<!-- -->
int res=0;
for(;x;x-=lowbit(x)) res + =tr[x];
return res;
}
}BIT;
struct SGT{<!-- -->
int seg[N<<2];
void modify(int l,int r,int x,int pos,int v){<!-- -->
if(l==r){<!-- --> seg[x]=max(seg[x],v);return;}
int mid=(l + r)>>1;
if(mid>=pos) modify(l,mid,x<<1,pos,v);
else modify(mid + 1,r,x<<1^1,pos,v);
seg[x]=max(seg[x<<1],seg[x<<1^1]);
}
int query(int l,int r,int x,int L,int R){<!-- -->
if(L<=l & amp; & amp;r<=R) return seg[x];
int mid=(l + r)>>1;
if(mid>=L & amp; & amp;mid<R) return max(query(l,mid,x<<1,L,R),query(mid + 1,r,x<<1^1, L,R));
if(mid>=L) return query(l,mid,x<<1,L,R);
return query(mid + 1,r,x<<1^1,L,R);
}
void upd(int pos,int v){<!-- --> modify(1,n,1,pos,v);}
int ask(int l1,int r1,int l2,int r2){<!-- -->
int ret=0;
if(l1<l2) ret=max(ret,query(1,n,1,l1,l2-1));
if(r2<r1) ret=max(ret,query(1,n,1,r2 + 1,r1));
return ret;
}
}sg;
void calc_f(int u){<!-- -->
for(int v:G[u]) calc_f(v),sum[u] + =f[v];
//u is not on the path
f[u]=sum[u];
//u is on the path
for(auto & amp;E:ln[u]){<!-- -->
E.w + =sum[u]-BIT.ask(Ldfn[E.u])-BIT.ask(Ldfn[E.v]);
f[u]=max(f[u],E.w);
//Single point addition + chain sum + properties of dfs -> subtree addition, single point check, single log
}
BIT.add(Ldfn[u],Rdfn[u],f[u]-sum[u]);
}
void calc_g(int u){<!-- -->
sort(ln[u].begin(),ln[u].end(),[ & amp;](Lines x,Lines y){<!-- --> return x.w>y.w;});
for(int v:G[u]){<!-- -->
g[v]=g[u] + sum[u]-f[v];
for(auto E:ln[u])
if(get_lca(E.u,v)!=v & amp; & amp;get_lca(E.v,v)!=v){<!-- -->//u,v does not have one end in the subtree of v
g[v]=max(g[v],E.w + g[u]-f[v]);break;
}
g[v]=max(g[v],sg.ask(Ldfn[u],Rdfn[u],Ldfn[v],Rdfn[v])-f[v]);
}
for(auto E:ln[u]) sg.upd(Ldfn[E.u],E.w + g[u]),sg.upd(Ldfn[E.v],E.w + g[u]);
for(int v:G[u]) calc_g(v);
}
void calc_ans(int u){<!-- -->
int res=0;
for(int v:G[u]) calc_ans(v),res=(res + siz[u]*siz[v])%P,siz[u] + =siz[v];
siz[u] + + ;
ans-=(g[u] + f[u])%P*(2*res + 2*siz[u]-1)%P;
res=(2*(siz[u]-1)*(n-siz[u])%P + 2*res + 2*n-1)%P;
ans + =(f[u]-sum[u])%P*res%P;
ans=(ans%P + P)%P;
}
void add(int x,int y){<!-- --> e[idx]=y,ne[idx]=h[x],h[x]=idx + + ;}
// int get_sum(int x,int y){<!-- -->
// int lca=get_lca(x,y),res=0;
// while(x!=lca) res + =f[x]-sum[x],x=up[x][0];
// while(y!=lca) res + =f[y]-sum[y],y=up[y][0];
// res + =f[lca]-sum[lca];
// return res;
// }
signed main(){<!-- -->
n=read(),m=read();
memset(h,-1,sizeof(h));
for(int i=1;i<n;i + + ){<!-- -->
int x=read(),y=read();
add(x,y),add(y,x);
}
predfs(1,-1);
for(int j=1;j<=18;j + + ) for(int i=1;i<=n;i + + ) up[i][j]=up[up[i][j-1 ]][j-1];
for(int i=1;i<=m;i + + ){<!-- -->
int u=read(),v=read(),w=read();
int lca=get_lca(u,v);
ln[lca].pb({<!-- -->u,v,w});
}
calc_f(1),calc_g(1),calc_ans(1);
ans=(ans + f[1]%P*n%P*n)%P;
// for(int i=1;i<=n;i + + ) for(int j=1;j<=n;j + + )
// ans + =f[1]-g[get_lca(i,j)]-f[get_lca(i,j)] + get_sum(i,j);
printf("%lld\
",ans);
fprintf(stderr,"%d ms\
",int64_t(1e3*clock()/CLOCKS_PER_SEC));
return 0;
}