有注释的一位题解

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
inline void print(char x) { putchar(x); }
inline void print(char *x) { while (x) putchar(x++); }
inline void print(const char x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
inline bool read(stdstring& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
inline void print(stdstring x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
inline void print(bool b) { putchar(b+48); }
template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define lson t[k].ls
#define rson t[k].rs
#define int long long
//对于两个点对，如果合法，那么其贡献为val=dis(u_1,v_1)+dis(u_2,v_2)+dis(u_1,u_2)+dis(v_1,v_2)-2cost_1-2cost_2
//继续转化我们设一点对中一个点的贡献为w(u)=dis(u,v)-2cost,对于v是一样的
//所以val=w(u_1)+w(u_2)+dis(u_1,u_2)+dis(v_1,v_2)
//此时如果我们加入v_1,v_2的lca
//那么式子为val=w(u_1)+w(u_2)+dis(u_1,u_2)+dis(v_1,rt)+dis(v_2,rt)-2dis(lca,rt)
//我们再次定义设w(u)=dis(u,v)-2cost+dis(v,rt)
//则val=w(u_1)+w(u_2)+dis(u_1,u_2)-2dis(lca,rt)
//那么对于每个点的w我们均可以预处理出来。
//而如果我们枚举lca，则2dis(lca,rt)为定值，那么我们需要维护的就只有dis(u_1,u_2)了

const int N=1e6+15;
const int inf=1e18;

int h[N],to[N],ne[N],w[N],idx=0;
int siz[N],son[N],fa[N],topfa[N],dep[N];
int in[N],out[N],dis[N],tim;
queue<int> rub;
vector<int> del[N];
struct pair_point
{
pair<int,int> u,v;
}ansp;
struct segment_tree
{
int ls,rs;
pair_point sum;
}t[N<<3];
int rt[N];
int n,m,T,cnt;
int ans;

void init()
{
while(!rub.empty())
rub.pop();
for(int i=1;i<=n;i++)
{
del[i].clear();
son[i]=fa[i]=0;
dis[i]=dep[i]=0;
fa[i]=topfa[i]=0;
in[i]=out[i]=0;
h[i]=-1;
rt[i]=0;
}
for(int i=1;i<=cnt;i++)
t[i].ls=t[i].rs=0,t[i].sum={{0,0},{0,0}};
tim=cnt=idx=0;
ans=-inf;
}

void add(int u,int v,int val)
{
to[++idx]=v;
ne[idx]=h[u];
h[u]=idx;
w[idx]=val;
}

void get_fa(int u,int f)
{
fa[u]=f;
siz[u]=1;
dep[u]=dep[f]+1;
in[u]=++tim;
for(int i=h[u];i!=-1;i=ne[i])
{
int v=to[i];
if(v==f)
continue;
dis[v]=dis[u]+w[i];
get_fa(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]||!son[u])
son[u]=v;
}
out[u]=tim;
}

void get_topfa(int u,int topf)
{
topfa[u]=topf;
if(son[u])
get_topfa(son[u],topf);
for(int i=h[u];i!=-1;i=ne[i])
{
int v=to[i];
if(vson[u]||vfa[u])
continue;
if(!topfa[v])
get_topfa(v,v);
}
}

pair<int,pair<int,int>> get_lca(int x,int y)
//返回<lca,<x->lca中lca的儿子 >,<y->lca 中lca的儿子>>
{
bool fl=0;
int resx=x;
int resy=y;
while(topfa[x]!=topfa[y])
{
if(dep[topfa[x]]<dep[topfa[y]])
swap(x,y),swap(resx,resy),fl^=1;
resx=topfa[x];
x=fa[topfa[x]];
}
int lca;
if(x==y)
lca=x;
else if(dep[x]<dep[y])
lca=x,resy=son[x];
else
lca=y,resx=son[y];
if(fl)
swap(resx,resy);
return {lca,{resx,resy}};
}

int new_node()
{
if(!rub.empty())
{
int l=rub.front();
rub.pop();
return l;
}
else
return ++cnt;
}

bool check(pair<int,int> x,pair<int,int> y,int &maxx)
{
if(x.first&&y.first)
{
int lca=get_lca(x.first,y.first).first;
int res=dis[x.first]+dis[y.first]-2*dis[lca]+x.second+y.second;
if(res>maxx)
{
maxx=res;
return 1;
}
else
return 0;
}
return 0;
}

int merge_ans(pair_point &ans,pair_point x,pair_point y)
{
if(!x.u.first&&!x.v.first)
{
ans=y;
return -inf;
}
if(!y.u.first&&!y.v.first)
{
ans=x;
return -inf;
}
int maxx=-inf;
int res;
int opt=0;
if(check(x.u,y.u,maxx))
opt=1;
if(check(x.u,y.v,maxx))
opt=2;
if(check(x.v,y.u,maxx))
opt=3;
if(check(x.v,y.v,maxx))
opt=4;
res=maxx;
if(check(x.u,x.v,maxx))
opt=5;
if(check(y.u,y.v,maxx))
opt=6;
if(opt1)
ans={x.u,y.u};
if(opt2)
ans={x.u,y.v};
if(opt3)
ans={x.v,y.u};
if(opt4)
ans={x.v,y.v};
if(opt5)
ans={x.u,x.v};
if(opt6)
ans={y.u,y.v};
return res;
}

void clear(int k)
{
t[k].ls=t[k].rs=0;
t[k].sum={{0,0},{0,0}};
rub.push(k);
}

void push_up(int k)
{
if(!lson||!rson)
t[k].sum=t[lson+rson].sum;
merge_ans(t[k].sum,t[lson].sum,t[rson].sum);
}

void update_add(int &k,int l,int r,int pos,pair<int,int> x)
{
if(!k)
k=new_node();
if(l==r)
{
t[k].sum.u=x;
return;
}
int mid=(l+r)>>1;
if(pos<=mid)
update_add(lson,l,mid,pos,x);
else
update_add(rson,mid+1,r,pos,x);
push_up(k);
}

void update_del(int &k,int l,int r,int pos)
{
if(!k)
k=new_node();
if(l==r)
{
t[k].sum.u={0,0};
return;
}
int mid=(l+r)>>1;
if(pos<=mid)
update_del(lson,l,mid,pos);
else
update_del(rson,mid+1,r,pos);
push_up(k);
}

int merge_tree(int x,int y)
{
if(!x||!y)
return x+y;
merge_ans(t[x].sum,t[x].sum,t[y].sum);
t[x].ls=merge_tree(t[x].ls,t[y].ls);
t[x].rs=merge_tree(t[x].rs,t[y].rs);
clear(y);
return x;
}

void get_ans(int u)
{
for(int i=h[u];i!=-1;i=ne[i])
{
int v=to[i];
if(v==fa[u])
continue;
get_ans(v);
ans=max(ans,merge_ans(ansp,t[rt[u]].sum,t[rt[v]].sum)-2*dis[u]);
rt[u]=merge_tree(rt[u],rt[v]);
}
for(auto v:del[u])
update_del(rt[u],1,m,v);
}

signed main()
{
// freopen("center.in","r",stdin);
// freopen("center.out","w",stdout);
cin>>T;
while(T--)
{
cin>>n;
init();
for(int i=1;i<n;i++)
{
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
get_fa(1,0);
get_topfa(1,1);
// int x,y;
// cin>>x>>y;
// cout<<get_dis(x,y);
cin>>m;
for(int i=1;i<=m;i++)
{
int u,v,cost;
cin>>u>>v>>cost;
pair<int,pair<int,int>> res=get_lca(u,v);
int lca=res.first;
int w=dis[u]+dis[v]-2dis[lca]-2cost;
int lu=res.second.first;
int lv=res.second.second;
// cout<<"e le mi "<<lca<<" "<<lu<<" "<<lv<<endl;
if(u!=lca)
{
pair<int,int> val={v,w+dis[u]};
ans=max(ans,merge_ans(ansp,{val,{0,0}},t[rt[u]].sum)-2dis[u]);
update_add(rt[u],1,m,i,val);
del[lu].push_back(i);
}
if(v!=lca)
{
pair<int,int> val={u,w+dis[v]};
ans=max(ans,merge_ans(ansp,{val,{0,0}},t[rt[v]].sum)-2dis[v]);
update_add(rt[v],1,m,i,val);
del[lv].push_back(i);
}
}
get_ans(1);
if(ans==-inf)
cout<<"F"<<endl;
else
cout<<ans/2<<endl;
}
return 0;
}