挖一个坑，待补题解。下附代码。
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int ll
typedef long long ll;
#define set0(x) memset(x,0,sizeof(x))
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
ll chkmax(ll &a,ll b){return a = a>b?a:b;}
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> VI;
template<typename T> void read(T &x){
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
read(first);
read(args...);
}
const int N = 100010;
int n,m,k,s[N],t[N],co[N],lc[N],u[N],v[N],w[N];
vector<int> G[N],G2[N],T[N];
struct work{
int depth;
ll ca,cb;
};
vector<work> E[N];
map<pii,int> dis;
ll d1[N];
int d[N];
int fa[N][19],dfn[N],sz[N],hom[N],seq[N],tim = 0,tim2 = 0;
namespace rmq {
const int MAXN = 1e5 + 5;
const int MAXLOG = 18;
int mi[MAXN][MAXLOG], lg[MAXN];
#define cmp(x,y) ((d[x] < d[y]) ? x : y)
inline int qmin(int l, int r) {
if(l>r)swap(l,r);
int tmp = lg[r - l + 1];
return cmp(mi[l][tmp], mi[r - (1 << tmp) + 1][tmp]);
}
void init(int *a, int n) {
for (int i = 1; i <= n; i++) {
mi[i][0] = a[i];
lg[i] = lg[i - 1] + ((1 << (lg[i-1] + 1)) <= i);
}
for (int t = 1; t < MAXLOG; t++)
for (int i = 1, j = (1 << (t - 1)) + 1; j <= n; i++, j++)
mi[i][t] = cmp(mi[i][t - 1], mi[j][t - 1]);
}
}
void dfs0(int num,int cf = 0){
dfn[num] = ++tim;
hom[num] = ++tim2;seq[tim2] = num;
sz[num] = 1;
for(auto ct:G[num]){
if(ct==cf)continue;
d1[ct] = d1[num]+dis[MP(num,ct)];
d[ct] = d[num]+1;
dfs0(ct,num);
seq[++tim2] = num;
sz[num]+=sz[ct];
}
}
inline int lca(int u,int v){
return rmq::qmin(hom[u],hom[v]);
}
inline ll dist(int u,int v){
return d1[u]+d1[v]-2*d1[lca(u,v)];
}
vector<pii> F[N];
struct node{
int ls,rs;
ll ma,mb;
}nds[10000010];
int cnt = 0,rts[N];
#define mid ((cl+cr)/2)
int newnode(){
++cnt;
nds[cnt].ls = nds[cnt].rs = 0;
nds[cnt].ma = nds[cnt].mb = -1e18;
return cnt;
}
void mrg(int id){
chkmax(nds[id].ma,max(nds[nds[id].ls].ma,nds[nds[id].rs].ma));
chkmax(nds[id].mb,max(nds[nds[id].ls].mb,nds[nds[id].rs].mb));
}
void destroy(int &id,int x,int cl = 0,int cr = n){
if(!id)return;
if(cl == cr){
nds[id].ma = nds[id].mb = -1e18;
return;
}
if(x<=mid)destroy(nds[id].ls,x,cl,mid);
else destroy(nds[id].rs,x,mid+1,cr);
nds[id].ma = max(nds[nds[id].ls].ma,nds[nds[id].rs].ma);
nds[id].mb = max(nds[nds[id].ls].mb,nds[nds[id].rs].mb);
}
void add(int &id,int x,ll va,ll vb,ll &cval,int cl = 0,int cr = n){
if(!id)id = newnode();
chkmax(nds[id].ma,va);
chkmax(nds[id].mb,vb);
if(cl == cr)return;
if(x<=mid){
add(nds[id].ls,x,va,vb,cval,cl,mid);
chkmax(cval,va+nds[nds[id].rs].mb);
}else{
add(nds[id].rs,x,va,vb,cval,mid+1,cr);
chkmax(cval,vb+nds[nds[id].ls].ma);
}
}
int merge(int a,int b,ll &cval){
if(!a || !b)return a|b;
chkmax(cval,nds[nds[a].ls].ma+nds[nds[b].rs].mb);
chkmax(cval,nds[nds[b].ls].ma+nds[nds[a].rs].mb);
chkmax(nds[a].ma,nds[b].ma);chkmax(nds[a].mb,nds[b].mb);
nds[a].ls = merge(nds[a].ls,nds[b].ls,cval);
nds[a].rs = merge(nds[a].rs,nds[b].rs,cval);
return a;
}
ll ans = -1e18;
int crt = 0;
void dfs(int num,int f = 0){
ll cval = -1e18;
for(auto ct:E[num]){
add(rts[num],ct.depth,ct.ca,ct.cb,cval);
}
for(auto ct:G[num]){
if(ct == f)continue;
dfs(ct,num);
merge(rts[num],rts[ct],cval);
}
ans = max(ans,cval-d1[num]);
destroy(rts[num],d[num]-1);
}
struct Mp{
int po = -1;
ll coef = -1e18;
Mp(){}
Mp(int a,ll b):po(a),coef(b){}
};
struct Pp{
Mp A,B;
Pp(){}
Pp(Mp A,Mp B):A(A),B(B){}
ll dis(){
if(A.po == -1 || B.po == -1){
return A.coef+B.coef;
}
return dist(A.po,B.po)+A.coef+B.coef;
}
};
Pp dfs1(int num){
Pp ret,nret;
auto chk = [&](Pp a){
if(a.dis()>nret.dis())nret = a;
};
for(auto ct:T[num]){
int nt = num^s[ct]^t[ct];
ll coef = dist(num,nt)-2*co[ct]+d1[num];
chk(Pp(ret.A,Mp(nt,coef)));
chk(Pp(ret.B,Mp(nt,coef)));
ret = nret;
}
if(num!=crt)ans = max(ans,nret.dis()/2-d1[num]);
for(auto ech:G2[num]){
Pp ct = dfs1(ech);
nret = Pp();
chk(Pp(ret.A,ct.A));
chk(Pp(ret.A,ct.B));
chk(Pp(ret.B,ct.A));
chk(Pp(ret.B,ct.B));
if(num!=crt)ans = max(ans,nret.dis()/2-d1[num]);
chk(ret);
chk(ct);
ret = nret;
}
return ret;
}
void solve(){
read(n);
for(int i=1;i<n;i++){
read(u[i],v[i],w[i]);
G[u[i]].PB(v[i]);
G[v[i]].PB(u[i]);
dis[MP(u[i],v[i])] = w[i];
dis[MP(v[i],u[i])] = w[i];
}
d[1] = 1;
dfs0(1);
rmq::init(seq,tim2);
read(m);
for(int i=0;i<m;i++){
read(s[i],t[i],co[i]);
lc[i] = lca(s[i],t[i]);
ll da = dist(s[i],t[i])-co[i],db = da+d1[lc[i]];
if(s[i]!=lc[i])E[s[i]].push_back({d[lc[i]],da,db});
if(t[i]!=lc[i])E[t[i]].push_back({d[lc[i]],da,db});
F[lc[i]].emplace_back(s[i],i);
F[lc[i]].emplace_back(t[i],i);
}
for(int i=1;i<=n;i++)rts[i] = newnode();
dfs(1);
auto cmp = [&](int a,int b)->bool{return dfn[a]<dfn[b];};
for(int i=1;i<=n;i++){
crt = i;
vector<int> cu,scope;
scope.PB(i);
for(auto ct:F[i]){
cu.PB(ct.F);
T[ct.F].PB(ct.S);
}
sort(all(cu),cmp);
cu.erase(unique(all(cu)),cu.end());
vector<int> stk;
stk.PB(i);
rts[i] = newnode();
auto pb = [&](int a){
rts[a] = newnode();
scope.PB(a);
stk.PB(a);
};
for(auto ct:cu){
int dd = lca(ct,stk.back());
while(d[stk.back()]>d[dd]){
if(d[stk[stk.size()-2]]>d[dd]) G2[stk[stk.size()-2]].PB(stk.back());
else G2[dd].PB(stk.back());
stk.pop_back();
}
if(d[stk.back()]<d[dd]) pb(dd);
if(d[stk.back()]<d[ct]) pb(ct);
}
while(stk.size()>=2){
G2[stk[stk.size()-2]].PB(stk.back());
stk.pop_back();
}
dfs1(i);
for(auto ct:scope){
G2[ct].clear();
rts[ct] = 0;
T[ct].clear();
}
}
}
void clear(){
if(ans<-1e16) cout<<"F\n";
else cout<<ans<<"\n";
for(int i=1;i<=n;i++){
E[i].clear();
F[i].clear();
G[i].clear();
}
cnt = 0;
dis.clear();
tim = tim2 = 0;
ans = -1e18;
}
signed main() {
nds[0].ma = nds[0].mb = -1e18;
int testcases;
read(testcases);
while(testcases--){
solve();
clear();
}
return 0;
}
发表回复