代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#ifndef DUCK_FASTIO_H
#define DUCK_FASTIO_H

typedef unsigned long duck_u64;
typedef long duck_i64;

typedef struct {
    duck_u64 abi_version;
    const char *stdin_ptr;
    duck_u64 stdin_size;
    char *stdout_ptr;
    duck_u64 stdout_limit;
    duck_u64 stdout_size;
    char *stderr_ptr;
    duck_u64 stderr_limit;
    duck_u64 stderr_size;
    const char *ib_ptr;
    duck_u64 ib_limit;
    char *ob_ptr;
    duck_u64 ob_limit;
    duck_u64 tsc_frequency;
} __attribute__((packed)) DuckInfo;

static __attribute__((always_inline)) inline DuckInfo *duck_info(long argc, char **argv) {
    char **p = argv + argc + 1;
    while (*p) ++p;
    duck_u64 *aux = (duck_u64 *)(p + 1);
    while (aux[0]) {
        if (aux[0] == 0x6b637564UL) return (DuckInfo *)aux[1];
        aux += 2;
    }
    return (DuckInfo *)0;
}

static __attribute__((always_inline)) inline duck_u64 duck_read_u64(const char **cursor) {
    const char *p = *cursor;
    while ((unsigned char)(*p - '0') > 9) ++p;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return value;
}

static __attribute__((always_inline)) inline duck_i64 duck_read_i64(const char **cursor) {
    const char *p = *cursor;
    while (*p != '-' && (unsigned char)(*p - '0') > 9) ++p;
    int negative = *p == '-';
    p += negative;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return negative ? -(duck_i64)value : (duck_i64)value;
}

static __attribute__((always_inline)) inline char *duck_write_u64(char *out, duck_u64 value) {
    char tmp[24];
    unsigned n = 0;
    do {
        tmp[n++] = (char)('0' + value % 10);
        value /= 10;
    } while (value);
    do *out++ = tmp[--n]; while (n);
    return out;
}

static __attribute__((always_inline)) inline char *duck_write_i64(char *out, duck_i64 value) {
    if (value < 0) {
        *out++ = '-';
        return duck_write_u64(out, (duck_u64)(-value));
    }
    return duck_write_u64(out, (duck_u64)value);
}

static __attribute__((always_inline, noreturn)) inline void duck_exit(void) {
    __asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall" ::: "rax", "rdi", "rcx", "r11", "memory");
    __builtin_unreachable();
}

#endif

using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
#define MAXN 50005
#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){
    extern const char *input_ptr;
    const char *s=input_ptr;
    while((unsigned char)(*s-'0')>9)++s;
    x=0;
    do{x=(x<<3)+(x<<1)+(*s++-'0');}while((unsigned char)(*s-'0')<=9);
    input_ptr=s;
}
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*2][20],od[MAXN],dfn[MAXN],rd[MAXN],ix,is_chain;
const char *input_ptr;char *output_ptr;
inline void write_answer(LL x){char q[24];int z=0;if(x<0)*output_ptr++='-',x=-x;do q[z++]=char('0'+x%10),x/=10;while(x);while(z)*output_ptr++=q[--z];*output_ptr++='\n';}
int ord[MAXN*2],lef[MAXN],rig[MAXN],lg[MAXN*2],root[MAXN];LL dis[MAXN],ans;
struct tann{int u,v,w;}rp[MAXN];
struct path{int x,y;LL v;}s[MAXN*2];
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){if(is_chain)return x<y?x: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;if(is_chain)return dis[x]>dis[y]?dis[x]-dis[y]:dis[y]-dis[x];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);
    }
}
int main(int argc,char **argv){
    DuckInfo *info=duck_info(argc,argv);input_ptr=info->stdin_ptr;output_ptr=info->stdout_ptr;
    read(TT);int testid=0;
    while(TT--){
        read(n);ans=-INF;is_chain=1;
        for(int i=1;i<n;i++){
            int u,v,w;read(u);read(v);read(w);
            if(u+1!=v)is_chain=0;
            addEdge(u,v,w);addEdge(v,u,w);rp[i]=(tann){u,v,w};
        }
        dosaka1(1,0);
        if(!is_chain){
            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)write_answer(ans/2);else *output_ptr++='F',*output_ptr++='\n';
        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();
        if(!is_chain)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;
    }
    info->stdout_size=(unsigned long)(output_ptr-info->stdout_ptr);duck_exit();
}

评测结果