情报中心

题解

首先，让我们先想想，如果两条路径相交的话，它们应该是长什么样子的。
大概是这样的：

也就是说，它们具有两个分割点，也就是相交路径的两端。
显然，肯定存在一个分割点是两条路径在它那边端点的$lca$。
我们不妨尝试在这个点上统计这两条路径的贡献。

但这贡献好像不是很好表示的样子呀，它重复的部分只会产生一次的贡献呀。
没事，我们不是有它的两个分割点吗？把两个分割点外的部分多统计一次，再除个$2$，中间就只会贡献一次了。
记这两条路径分别为$(u_1,v_1,w_1),(u_2,v_2,w_2)$，其中$u_1$与$u_2$相邻，$v_1$与$v_2$相邻。
显然，我们的贡献为$\frac{1}{2}(dis(u_1,v_1)+dis(u_2,v_2)+dis(u_1,u_2)+dis(v_1,v_2)-w_1-w_2)$。
由于我们是在$u_1,u_2$的$lca$统计的答案，所以可以把$dis(u_1,u_2)$拆成$de{p}_{u_1}+de{p}_{u_2}-2de{p}_{lca(u_1,u_2)}$。
这样的话，我们就是要最小化$(de{p}_{u_1}+dis(u_1,v_1)-w_1)+(de{p}_{u_2}+dis(u_2,v_2)-w_2)+dis(v_1,v_2)$。
前面这两个东西分别与这两条路径各自相关，而涉及到它们两者的就只剩下后面这个$dis(v_1,v_2)$了。
我们完全可以把两条路径的贡献插在$v_1,v_2$上，这样每次就只需要在子树的外边询问一个带权最远点对。

带权最远点对好维护，我们记$diam(S)$表示集合$S$内的最远点对，显然有，$diam(A+B)=diam(diam(A)+diam(B))$。
也就是说，我们可以采用$dfs$序线段树的形式，在每个节点上维护$dfs$序在这个区间内的点的带权最远点对。
往上$pushup$的时候，只需要合并两个子区间的最远点对即可。
当然，维护最远点对的合并显然就要块数求出两点之间的距离，这也就意味着我们还得打一个$O(1)$的$lca$。
当然，我们要让两条路径刚好在$lca$上统计，所以其实是在线段树合并的时候统计的两个集合之间贡献的答案。

时间复杂化度$O\left(m\log n\right)$。

源码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
#define MAXN 100005
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
const LL INF=0x3f3f3f3f3f3f3f3f;
const int mo=998244353;
template<typename _T>
void read(_T &x){
    _T f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
    x*=f;
}
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1)t=1ll*a*t%p;a=1ll*a*a%p;s>>=1;}return t;}
int TT,n,m,head[MAXN],Tot,dep[MAXN],idx,st[MAXN][20],od[MAXN],dfn[MAXN],rd[MAXN],ix;
int ord[MAXN],lef[MAXN],rig[MAXN],lg[MAXN],root[MAXN];LL dis[MAXN],ans;
struct tann{int u,v,w;}rp[MAXN];
struct path{int x,y;LL v;}s[MAXN];
struct edge{int to,nxt,paid;}e[MAXN<<1];
void addEdge(int u,int v,int w){e[++Tot]=(edge){v,head[u],w};head[u]=Tot;}
void dosaka1(int u,int fa){
    ord[++idx]=u;lef[u]=idx;dep[u]=dep[fa]+1;dfn[u]=++ix;od[ix]=u;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;if(v==fa)continue;
        dis[v]=dis[u]+e[i].paid;dosaka1(v,u);ord[++idx]=u;
    }
    rig[u]=idx;rd[u]=ix;
}
int Min(int x,int y){return dep[x]<dep[y]?x:y;}
int ask(int l,int r){int len=lg[r-l+1];return Min(st[l][len],st[r-(1<<len)+1][len]);}
int lca(int x,int y){int res=ask(min(lef[x],lef[y]),max(rig[x],rig[y]));return res;}
LL dist(int x,int y){if(!x||!y)return -INF;int x_y=lca(x,y);return dis[x]+dis[y]-dis[x_y]*2;}
struct node{
    int x,y;LL vx,vy;node(){x=y=0;vx=vy=-INF;}
    node(int X,int Y,LL Vx,LL Vy){x=X;y=Y;vx=Vx;vy=Vy;}
};
node calc(node x,node y){
    int X1=x.x,Y1=x.y,X2=y.x,Y2=y.y;node res;
    if(!X1&&!X2)return res;if(!X2)return x;if(!X1)return y;
    LL d1=dist(X1,Y1)+x.vx+x.vy,d2=dist(X1,X2)+x.vx+y.vx;
    LL d3=dist(X1,Y2)+x.vx+y.vy,d4=dist(Y1,X2)+x.vy+y.vx;
    LL d5=dist(Y1,Y2)+x.vy+y.vy,d6=dist(X2,Y2)+y.vx+y.vy;
    LL maxx=max(max(d1,d2),max(max(d3,d4),max(d5,d6)));
    if(maxx==d1)res=x;else if(maxx==d6)res=y;
    else if(maxx==d2)res=node(X1,X2,x.vx,y.vx);
    else if(maxx==d3)res=node(X1,Y2,x.vx,y.vy);
    else if(maxx==d4)res=node(Y1,X2,x.vy,y.vx);
    else res=node(Y1,Y2,x.vy,y.vy);
    if(res.x==res.y&&res.vx<res.vy)swap(res.vx,res.vy);
    return res;
}
struct ming{int lson,rson;node val;};
vector<int>vec[MAXN];
class SegmentTree{
    private:
        ming tr[MAXN*40];int tot;
    public:
        void insert(int &rt,int l,int r,int ai,LL aw){
            if(l>r||l>ai||r<ai)return ;if(!rt)rt=++tot;
            if(l==r){
                if(tr[rt].val.vx<aw)
                    tr[rt].val.y=tr[rt].val.x,tr[rt].val.vy=tr[rt].val.vx,
                    tr[rt].val.x=od[ai],tr[rt].val.vx=aw;
                else if(tr[rt].val.vy<aw)
                    tr[rt].val.y=od[ai],tr[rt].val.vy=aw;
                return ;
            }
            int mid=l+r>>1;
            if(ai<=mid)insert(tr[rt].lson,l,mid,ai,aw);
            if(ai>mid)insert(tr[rt].rson,mid+1,r,ai,aw);
            tr[rt].val=calc(tr[tr[rt].lson].val,tr[tr[rt].rson].val);
        }
        int merge(int x,int y,int l,int r){
            if(!x||!y)return x+y;
            tr[x].val=calc(tr[x].val,tr[y].val);
            if(l==r)return x;int mid=l+r>>1;
            tr[x].lson=merge(tr[x].lson,tr[y].lson,l,mid);
            tr[x].rson=merge(tr[x].rson,tr[y].rson,mid+1,r);
            return x;
        }
        node query(int rt,int l,int r,int al,int ar){
            if(l>r||l>ar||r<al||al>ar||!rt)return node();
            if(al<=l&&r<=ar)return tr[rt].val;int mid=l+r>>1;
            if(ar<=mid)return query(tr[rt].lson,l,mid,al,ar);
            if(al>mid)return query(tr[rt].rson,mid+1,r,al,ar);
            return calc(query(tr[rt].lson,l,mid,al,ar),query(tr[rt].rson,mid+1,r,al,ar));
        }
        void clear(){
            for(int i=1;i<=tot;i++)
                tr[i].lson=tr[i].rson=0,tr[i].val=node();
            tot=0;
        }
}T;
LL work(int u,LL tu,int v,LL tv){
    if(!u||!v)return -INF;
    LL res=dist(u,v)+tu+tv;
    return res;
}
void dosaka2(int u,int fa){
    LL tp=-2ll*dis[u];
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;if(v==fa)continue;dosaka2(v,u);
        node tmp1=calc(T.query(root[u],1,n,1,dfn[u]-1),T.query(root[u],1,n,rd[u]+1,n));
        node tmp2=calc(T.query(root[v],1,n,1,dfn[u]-1),T.query(root[v],1,n,rd[u]+1,n));
        ans=max(ans,work(tmp1.x,tmp1.vx,tmp2.x,tmp2.vx)+tp);
        ans=max(ans,work(tmp1.x,tmp1.vx,tmp2.y,tmp2.vy)+tp);
        ans=max(ans,work(tmp1.y,tmp1.vy,tmp2.x,tmp2.vx)+tp);
        ans=max(ans,work(tmp1.y,tmp1.vy,tmp2.y,tmp2.vy)+tp);
        root[u]=T.merge(root[u],root[v],1,n);
    }
    int siz=vec[u].size();
    for(int i=0;i<siz;i++){
        int id=vec[u][i],x=s[id].x,y=s[id].y,z=x+y-u;
        if(dfn[u]<=dfn[z]&&dfn[z]<=rd[u])continue;
        LL w=-2ll*s[id].v+dist(x,y)+dis[u];
        node tmp=calc(T.query(root[u],1,n,1,dfn[u]-1),T.query(root[u],1,n,rd[u]+1,n));
        ans=max(ans,work(z,w,tmp.x,tmp.vx)+tp);
        ans=max(ans,work(z,w,tmp.y,tmp.vy)+tp);
        T.insert(root[u],1,n,dfn[z],w);
    }
}
signed main(){
    freopen("center.in","r",stdin);
    freopen("center.out","w",stdout);
    read(TT);int testid=0;
    while(TT--){
        read(n);ans=-INF;
        for(int i=1;i<n;i++){
            int u,v,w;read(u);read(v);read(w);
            addEdge(u,v,w);addEdge(v,u,w);rp[i]=(tann){u,v,w};
        }
        dosaka1(1,0);
        for(int i=1;i<=idx;i++)st[i][0]=ord[i];
        for(int i=2;i<=idx;i++)lg[i]=lg[i>>1]+1;
        for(int i=1;i<=lg[idx];i++)
            for(int j=1;j<=idx-(1<<i)+1;j++)
                st[j][i]=Min(st[j][i-1],st[j+(1<<i-1)][i-1]);
        read(m);
        for(int i=1;i<=m;i++)read(s[i].x),read(s[i].y),read(s[i].v),
            vec[s[i].x].pb(i),vec[s[i].y].pb(i);
        dosaka2(1,0);if(ans>-INF+1)printf("%lld\n",ans/2);else puts("F");
        for(int i=1;i<=idx;i++)od[i]=0;
        for(int i=1;i<=n;i++)lef[i]=rig[i]=dis[i]=dep[i]=dfn[i]=rd[i]=head[i]=root[i]=0,vec[i].clear();
        for(int i=0;i<=lg[idx];i++)
            for(int j=1;j<=idx-(1<<i)+1;j++)st[j][i]=0;
        T.clear();idx=ix=Tot=0;
    }
    return 0;
}
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

谢谢！！！