代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ppp pair<int,pair<int,ll> >
#define X first
#define Y second
const int N=1e5+5; 
const ll inf=1e17;
int n,m,cc,T,tt,nn,tp,dep[N],vis[N],lg[N<<1],f[N<<1][20],dfn[N],t[N],st[N],hd[N],rt[N],ls[N*40],rs[N*40];
ll ans,d[N],mx1[N*40],mx2[N*40];
vector<int>g[N];vector<ppp>v[N];
struct E{int v,nxt;ll w;}e[N<<1];
inline void add(int u,int v,ll w){e[++cc]=(E){v,hd[u],w};hd[u]=cc;}
void dfs(int x){f[++T][0]=x;dfn[x]=T;for(int i=hd[x];i;i=e[i].nxt){int y=e[i].v;dep[y]=dep[x]+1;d[y]=d[x]+e[i].w;dfs(y);f[++T][0]=x;}}
inline int mn(int u,int v){return dep[u]<dep[v]?u:v;}
inline int lca(int u,int v){u=dfn[u];v=dfn[v];if(u>v)swap(u,v);int d=lg[v-u+1];return mn(f[u][d],f[v-(1<<d)+1][d]);}
inline ll dis(int u,int v){return d[u]+d[v]-d[lca(u,v)]*2;}
inline int nwnd(){int x=++tt;ls[x]=rs[x]=0;mx1[x]=mx2[x]=-inf;return x;}
inline void up(int x){mx1[x]=max(mx1[ls[x]],mx1[rs[x]]);mx2[x]=max(mx2[ls[x]],mx2[rs[x]]);}
void upd(int&x,int l,int r,int p,ll v1,ll v2,ll d)
{
    if(!x)x=nwnd();mx1[x]=max(mx1[x],v1);mx2[x]=max(mx2[x],v2);if(l==r)return;
    int mid=l+r>>1;if(p<=mid){ans=max(ans,v1+mx2[rs[x]]-d);upd(ls[x],l,mid,p,v1,v2,d);}
    else {ans=max(ans,v2+mx1[ls[x]]-d);upd(rs[x],mid+1,r,p,v1,v2,d);} 
}
int merge(int x,int y,int l,int r,ll d)
{
    if(!x||!y)return x+y;int mid=l+r>>1;
    if(l==r){mx1[x]=max(mx1[x],mx1[y]);mx2[x]=max(mx2[x],mx2[y]);return x;}
    ans=max(ans,mx1[ls[x]]+mx2[rs[y]]-d);ans=max(ans,mx1[ls[y]]+mx2[rs[x]]-d);
    ls[x]=merge(ls[x],ls[y],l,mid,d);rs[x]=merge(rs[x],rs[y],mid+1,r,d);up(x);return x;
} 
void cut(int&x,int l,int r,int p)
{
    if(!x)return;if(l==r){x=0;return;}int mid=l+r>>1;
    if(p<=mid)rs[x]=0,cut(ls[x],l,mid,p);else cut(rs[x],mid+1,r,p);up(x);
}
void dfs1(int x){for(int i=hd[x],y;i;i=e[i].nxt)dfs1(y=e[i].v),rt[x]=merge(rt[x],rt[y],1,n,d[x]);cut(rt[x],1,n,dep[x]-1);}
struct dia
{
    int u[2];ll v[2],l;dia(){u[0]=u[1]=0;v[0]=v[1]=l=-inf;}
    dia(int x,ll w){u[0]=x;v[0]=w;u[1]=0;v[1]=-inf;l=-inf;}
}tr[N];
inline bool cmp(ppp x,ppp y){return dfn[x.X]<dfn[y.X];}
inline dia merge(dia x,dia y,ll d)
{
    dia r;ll w;r=x.l>y.l?x:y;
    for(int i=0;i<2;i++)if(x.u[i])for(int j=0;j<2;j++)if(y.u[j])
    {
        w=dis(x.u[i],y.u[j])+x.v[i]+y.v[j];ans=max(ans,(w-d)/2);
        if(w>r.l){r.u[0]=x.u[i];r.u[1]=y.u[j];r.v[0]=x.v[i];r.v[1]=y.v[j];r.l=w;}
    }
    return r;
}
void dfss(int x,int rt){for(int i=0;i<g[x].size();i++){int y=g[x][i];dfss(y,rt);if(x!=rt)tr[x]=merge(tr[x],tr[y],d[x]*2);}vis[x]=0;g[x].clear();}
inline void ins(int x)
{
    int y=lca(x,st[tp]);if(!vis[y]){vis[y]=1;t[++nn]=y;}
    while(tp>1&&dep[st[tp-1]]>=dep[y])g[st[tp-1]].push_back(st[tp]),tp--;
    if(st[tp]!=y)g[y].push_back(st[tp]),st[tp]=y;st[++tp]=x;
} 
void sol()
{
    scanf("%d",&n);ans=-inf;cc=T=tt=0;dep[1]=1;
    for(int i=1;i<=n;i++)hd[i]=0,rt[i]=0,v[i].clear();
    for(int i=1;i<n;i++){int u,v;ll w;scanf("%d%d%lld",&u,&v,&w);add(u,v,w);}
    dfs(1);scanf("%d",&m);for(int i=2;i<=T;i++)lg[i]=lg[i>>1]+1;
    for(int j=1;j<=18;j++)for(int i=1;i+(1<<j)-1<=T;i++)f[i][j]=mn(f[i][j-1],f[i+(1<<j-1)][j-1]);
    for(int i=1;i<=m;i++)
    {
        int x,y,t;ll z;scanf("%d%d%lld",&x,&y,&z);t=lca(x,y);ll w=dis(x,y)-z;
        if(x!=t)upd(rt[x],1,n,dep[t],w,w+d[t],d[x]),v[t].push_back(make_pair(x,make_pair(y,w+d[x]-z)));
        if(y!=t)upd(rt[y],1,n,dep[t],w,w+d[t],d[y]),v[t].push_back(make_pair(y,make_pair(x,w+d[y]-z)));
    }
    dfs1(1);
    for(int i=1;i<=n;i++)
    {
        sort(v[i].begin(),v[i].end(),cmp);tp=nn=0;st[++tp]=i;vis[i]=1;t[++nn]=i;
        for(int j=0;j<v[i].size();j++)if(!vis[v[i][j].X]){vis[v[i][j].X]=1;t[++nn]=v[i][j].X;ins(v[i][j].X);}
        while(tp>1){g[st[tp-1]].push_back(st[tp]);tp--;}
        for(int j=1;j<=nn;j++){int x=t[j];tr[x].u[0]=tr[x].u[1]=0;tr[x].v[0]=tr[x].v[1]=tr[x].l=-inf;}
        for(int j=0;j<v[i].size();j++){dia x=dia(v[i][j].Y.X,v[i][j].Y.Y);tr[v[i][j].X]=merge(tr[v[i][j].X],x,d[v[i][j].X]*2);}
        dfss(i,i);
    }
    if(ans<=-1e16)puts("F");else printf("%lld\n",ans);
}
int main()
{
    mx1[0]=mx2[0]=-inf;int T;scanf("%d",&T);while(T--)sol();return 0;
}

评测结果