\u6316\u4e00\u4e2a\u5751\uff0c\u5f85\u8865\u9898\u89e3\u3002\u4e0b\u9644\u4ee3\u7801\u3002<\/p>\n\n\n\n\n\n\n\n
#pragma comment(linker, \"\/stack:200000000\")\n#pragma GCC optimize(\"Ofast,no-stack-protector\")\n#pragma GCC target(\"sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native\")\n#pragma GCC optimize(\"unroll-loops\")\n#include <bits\/stdc++.h>\n\n\nusing namespace std;\n#define int ll\ntypedef long long ll;\n#define set0(x) memset(x,0,sizeof(x))\n#define F first\n#define S second\n#define PB push_back\n#define MP make_pair\n#define rep(i, a, b) for(int i = a; i < (b); ++i)\n#define trav(a, x) for(auto& a : x)\n#define all(x) x.begin(), x.end()\n#define sz(x) (int)(x).size()\n\nll chkmax(ll &a,ll b){return a = a>b?a:b;}\ntypedef long long ll;\ntypedef pair<int,int> pii;\ntypedef pair<ll,ll> pll;\ntypedef vector<int> VI;\ntemplate<typename T> void read(T &x){\n\tx = 0;char ch = getchar();ll f = 1;\n\twhile(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}\n\twhile(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;\n}\ntemplate<typename T, typename... Args> void read(T &first, Args& ... args) {\n\tread(first);\n\tread(args...);\n}\n\nconst int N = 100010;\nint n,m,k,s[N],t[N],co[N],lc[N],u[N],v[N],w[N];\nvector<int> G[N],G2[N],T[N];\nstruct work{\n\tint depth;\n\tll ca,cb;\n};\nvector<work> E[N];\nmap<pii,int> dis;\n\nll d1[N];\nint d[N];\nint fa[N][19],dfn[N],sz[N],hom[N],seq[N],tim = 0,tim2 = 0;\n\nnamespace rmq {\n\tconst int MAXN = 1e5 + 5;\n\tconst int MAXLOG = 18;\n\tint mi[MAXN][MAXLOG], lg[MAXN];\n\t#define cmp(x,y) ((d[x] < d[y]) ? x : y)\n\tinline int qmin(int l, int r) {\n\t\tif(l>r)swap(l,r);\n\t\tint tmp = lg[r - l + 1];\n\t\treturn cmp(mi[l][tmp], mi[r - (1 << tmp) + 1][tmp]);\n\t}\n\tvoid init(int *a, int n) {\n\t\tfor (int i = 1; i <= n; i++) {\n\t\t\tmi[i][0] = a[i];\n\t\t\tlg[i] = lg[i - 1] + ((1 << (lg[i-1] + 1)) <= i);\n\t\t}\n\t\tfor (int t = 1; t < MAXLOG; t++)\n\t\tfor (int i = 1, j = (1 << (t - 1)) + 1; j <= n; i++, j++)\n\t\t\tmi[i][t] = cmp(mi[i][t - 1], mi[j][t - 1]);\n\t}\n}\n\nvoid dfs0(int num,int cf = 0){\n\tdfn[num] = ++tim;\n\thom[num] = ++tim2;seq[tim2] = num;\n\tsz[num] = 1;\n\tfor(auto ct:G[num]){\n\t\tif(ct==cf)continue;\n\t\td1[ct] = d1[num]+dis[MP(num,ct)];\n\t\td[ct] = d[num]+1;\n\t\tdfs0(ct,num);\n\t\tseq[++tim2] = num;\n\t\tsz[num]+=sz[ct];\n\t}\n}\n\ninline int lca(int u,int v){\n\treturn rmq::qmin(hom[u],hom[v]);\n}\ninline ll dist(int u,int v){\n\treturn d1[u]+d1[v]-2*d1[lca(u,v)];\n}\nvector<pii> F[N];\n\nstruct node{\n\tint ls,rs;\n\tll ma,mb;\n}nds[10000010];\nint cnt = 0,rts[N];\n\n#define mid ((cl+cr)\/2)\nint newnode(){\n\t++cnt;\n\tnds[cnt].ls = nds[cnt].rs = 0;\n\tnds[cnt].ma = nds[cnt].mb = -1e18;\n\treturn cnt;\n}\nvoid mrg(int id){\n\tchkmax(nds[id].ma,max(nds[nds[id].ls].ma,nds[nds[id].rs].ma));\n\tchkmax(nds[id].mb,max(nds[nds[id].ls].mb,nds[nds[id].rs].mb));\n}\nvoid destroy(int &id,int x,int cl = 0,int cr = n){\n\tif(!id)return;\n\tif(cl == cr){\n\t\tnds[id].ma = nds[id].mb = -1e18;\n\t\treturn;\n\t}\n\tif(x<=mid)destroy(nds[id].ls,x,cl,mid);\n\telse destroy(nds[id].rs,x,mid+1,cr);\n\tnds[id].ma = max(nds[nds[id].ls].ma,nds[nds[id].rs].ma);\n\tnds[id].mb = max(nds[nds[id].ls].mb,nds[nds[id].rs].mb);\n}\nvoid add(int &id,int x,ll va,ll vb,ll &cval,int cl = 0,int cr = n){\n\tif(!id)id = newnode();\n\tchkmax(nds[id].ma,va);\n\tchkmax(nds[id].mb,vb);\n\tif(cl == cr)return;\n\tif(x<=mid){\n\t\tadd(nds[id].ls,x,va,vb,cval,cl,mid);\n\t\tchkmax(cval,va+nds[nds[id].rs].mb);\n\t}else{\n\t\tadd(nds[id].rs,x,va,vb,cval,mid+1,cr);\n\t\tchkmax(cval,vb+nds[nds[id].ls].ma);\n\t}\n}\nint merge(int a,int b,ll &cval){\n\tif(!a || !b)return a|b;\n\tchkmax(cval,nds[nds[a].ls].ma+nds[nds[b].rs].mb);\n\tchkmax(cval,nds[nds[b].ls].ma+nds[nds[a].rs].mb);\n\tchkmax(nds[a].ma,nds[b].ma);chkmax(nds[a].mb,nds[b].mb);\n\tnds[a].ls = merge(nds[a].ls,nds[b].ls,cval);\n\tnds[a].rs = merge(nds[a].rs,nds[b].rs,cval);\n\treturn a;\n}\nll ans = -1e18;\nint crt = 0;\nvoid dfs(int num,int f = 0){\n\tll cval = -1e18;\n\tfor(auto ct:E[num]){\n\t\tadd(rts[num],ct.depth,ct.ca,ct.cb,cval);\n\t}\n\tfor(auto ct:G[num]){\n\t\tif(ct == f)continue;\n\t\tdfs(ct,num);\n\t\tmerge(rts[num],rts[ct],cval);\n\t}\n\tans = max(ans,cval-d1[num]);\n\tdestroy(rts[num],d[num]-1);\n}\n\nstruct Mp{\n\tint po = -1;\n\tll coef = -1e18;\n\tMp(){}\n\tMp(int a,ll b):po(a),coef(b){}\n};\nstruct Pp{\n\tMp A,B;\n\tPp(){}\n\tPp(Mp A,Mp B):A(A),B(B){}\n\tll dis(){\n\t\tif(A.po == -1 || B.po == -1){\n\t\t\treturn A.coef+B.coef;\n\t\t}\n\t\treturn dist(A.po,B.po)+A.coef+B.coef;\n\t}\n};\nPp dfs1(int num){\n\tPp ret,nret;\n\tauto chk = [&](Pp a){\n\t\tif(a.dis()>nret.dis())nret = a;\n\t};\n\tfor(auto ct:T[num]){\n\t\tint nt = num^s[ct]^t[ct];\n\t\tll coef = dist(num,nt)-2*co[ct]+d1[num];\n\t\tchk(Pp(ret.A,Mp(nt,coef)));\n\t\tchk(Pp(ret.B,Mp(nt,coef)));\n\t\tret = nret;\n\t}\n\tif(num!=crt)ans = max(ans,nret.dis()\/2-d1[num]);\n\tfor(auto ech:G2[num]){\n\t\tPp ct = dfs1(ech);\n\t\tnret = Pp();\n\t\tchk(Pp(ret.A,ct.A));\n\t\tchk(Pp(ret.A,ct.B));\n\t\tchk(Pp(ret.B,ct.A));\n\t\tchk(Pp(ret.B,ct.B));\n\t\tif(num!=crt)ans = max(ans,nret.dis()\/2-d1[num]);\n\t\tchk(ret);\n\t\tchk(ct);\n\t\tret = nret;\n\t}\n\treturn ret;\n}\n\nvoid solve(){\n\tread(n);\n\tfor(int i=1;i<n;i++){\n\t\tread(u[i],v[i],w[i]);\n\t\tG[u[i]].PB(v[i]);\n\t\tG[v[i]].PB(u[i]);\n\t\tdis[MP(u[i],v[i])] = w[i];\n\t\tdis[MP(v[i],u[i])] = w[i];\n\t}\n\td[1] = 1;\n\tdfs0(1);\n\trmq::init(seq,tim2);\n\tread(m);\n\tfor(int i=0;i<m;i++){\n\t\tread(s[i],t[i],co[i]);\n\t\tlc[i] = lca(s[i],t[i]);\n\t\tll da = dist(s[i],t[i])-co[i],db = da+d1[lc[i]];\n\t\tif(s[i]!=lc[i])E[s[i]].push_back({d[lc[i]],da,db});\n\t\tif(t[i]!=lc[i])E[t[i]].push_back({d[lc[i]],da,db});\n\t\tF[lc[i]].emplace_back(s[i],i);\n\t\tF[lc[i]].emplace_back(t[i],i);\n\t}\n\tfor(int i=1;i<=n;i++)rts[i] = newnode();\n\tdfs(1);\n\tauto cmp = [&](int a,int b)->bool{return dfn[a]<dfn[b];};\n\t\n\tfor(int i=1;i<=n;i++){\n\t\tcrt = i;\n\t\tvector<int> cu,scope;\n\t\tscope.PB(i);\n\t\tfor(auto ct:F[i]){\n\t\t\tcu.PB(ct.F);\n\t\t\tT[ct.F].PB(ct.S);\n\t\t}\n\t\tsort(all(cu),cmp);\n\t\tcu.erase(unique(all(cu)),cu.end());\n\t\tvector<int> stk;\n\t\tstk.PB(i);\n\t\trts[i] = newnode();\n\t\tauto pb = [&](int a){\n\t\t\trts[a] = newnode();\n\t\t\tscope.PB(a);\n\t\t\tstk.PB(a);\n\t\t};\n\t\tfor(auto ct:cu){\n\t\t\tint dd = lca(ct,stk.back());\n\t\t\twhile(d[stk.back()]>d[dd]){\n\t\t\t\tif(d[stk[stk.size()-2]]>d[dd]) G2[stk[stk.size()-2]].PB(stk.back());\n\t\t\t\telse G2[dd].PB(stk.back());\n\t\t\t\tstk.pop_back();\n\t\t\t}\n\t\t\tif(d[stk.back()]<d[dd]) pb(dd);\n\t\t\tif(d[stk.back()]<d[ct]) pb(ct);\n\t\t}\n\t\twhile(stk.size()>=2){\n\t\t\tG2[stk[stk.size()-2]].PB(stk.back());\n\t\t\tstk.pop_back();\n\t\t}\n\t\tdfs1(i);\n\t\tfor(auto ct:scope){\n\t\t\tG2[ct].clear();\n\t\t\trts[ct] = 0;\n\t\t\tT[ct].clear();\n\t\t}\n\t}\n}\n\nvoid clear(){\n\tif(ans<-1e16) cout<<\"F\\n\";\n\telse cout<<ans<<\"\\n\";\n\tfor(int i=1;i<=n;i++){\n\t\tE[i].clear();\n\t\tF[i].clear();\n\t\tG[i].clear();\n\t}\n\tcnt = 0;\n\tdis.clear();\n\ttim = tim2 = 0;\n\tans = -1e18;\n}\nsigned main() {\n\tnds[0].ma = nds[0].mb = -1e18;\n\tint testcases;\n\tread(testcases);\n\twhile(testcases--){\n\t\tsolve();\n\t\tclear();\n\t}\n\treturn 0;\n}\n<\/code><\/pre>\n ","protected":false},"excerpt":{"rendered":"\u6316\u4e00\u4e2a\u5751\uff0c\u5f85\u8865\u9898\u89e3\u3002\u4e0b\u9644\u4ee3\u7801\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/353"}],"collection":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=353"}],"version-history":[{"count":1,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/353\/revisions"}],"predecessor-version":[{"id":354,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/353\/revisions\/354"}],"wp:attachment":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=353"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=353"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=353"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}