P4775 [NOI2018] Intelligence Center (Line Segment Tree Merging)

前言

似乎也没有那么难？
But it also don't want to.

解析

For the two cross path $(u_1,v_1,c_1),(u_2,v_2,c_2)$,设 $t=lca(u_1,u_1)$ 为四个 lca 中最深的,So the cost of二倍可以写为 $dis(u_1,v_1)+dis(u_2,v_2)+dis(u_1,u_2)+dis(v_1,v_2)-2c_1-2c_2$.
枚举 $t$ 的位置,Distance can be written as $dis(u_1,v_1)+de{p}_{u_1}-2c_1+dis(u_2,v_2)+de{p}_{u_2}-2c_2+dis(v_1,v_2)-2de{p}_t$,可以看成 $dis(v_1,v_2)+w_1+w_2-2de{p}_t$ 的形式.
See maximum distance,Easy to think of line segment tree maintenance of the diameter of the classical approach.
Can be seen as new“ $v_1$” Is the original point out a length of $w_1$ 的边,So still can be depicted as a tree structure,Although there is a negative right side,But due to the negative right side there must be an endpoint is leaves,So the original conclusion or right.

Each node maintains subtree within“v”节点集合,Merge to update the answer,Line segment tree merge again can,时空复杂度 $O(m\log m+n\log n)$.

Remember to arrive again lca The point before delete.

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("line: %d\n",__LINE__)

inline ll read(){
    
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)) {
    if(c=='-')f=-1;c=getchar();}
  while(isdigit(c)) {
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}
bool mem1;

const int N=2e5+100;
const ll inf=2e18;
const int mod=998244353;
const bool Flag=0;

#define add(x,y) ((((x)+=(y))>=mod)&&((x)-=mod))
inline ll ksm(ll x,ll k){
    
  ll res(1);
  while(k){
    
    if(k&1) res=res*x%mod;
    x=x*x%mod;
    k>>=1;
  }
  return res;
}

int n,m;

struct edge{
    
  int to,nxt,w;
}p[N<<1];
int fi[N],cnt;
inline void addline(int x,int y,int w){
    
  p[++cnt]=(edge){
    y,fi[x],w};fi[x]=cnt;
}
int q[N],dep[N],tim,pos[N];
ll dis[N];

int pl[N][20];
inline int jump(int x,int anc){
    
  if(Flag) printf("jump: x=%d anc=%d\n",x,anc);
  for(int k=16;k>=0;k--){
    
    if(dep[pl[x][k]]<=dep[anc]) continue;
    x=pl[x][k];
  }
  if(Flag) printf(" p=%d\n",x);
  return x;
}

void dfs(int x,int f){
    
  dep[x]=dep[f]+1;
  pos[x]=++tim;
  q[tim]=x;
  pl[x][0]=f;
  for(int k=1;pl[x][k-1];k++) pl[x][k]=pl[pl[x][k-1]][k-1];
  for(int i=fi[x];~i;i=p[i].nxt){
    
    int to=p[i].to;
    if(to==f) continue;
    dis[to]=dis[x]+p[i].w;
    dfs(to,x);
    q[++tim]=x;
  }
  return;
}
int mn[N][20],lg[N],mi[20];
inline int cmp(int x,int y){
    return dep[x]<dep[y]?x:y;}
void ST(){
    
  lg[0]=-1;
  for(int i=1;i<=tim;i++) lg[i]=lg[i>>1]+1;
  mi[0]=1;
  for(int i=1;i<=lg[tim];i++) mi[i]=mi[i-1]<<1;
  for(int i=1;i<=tim;i++) mn[i][0]=q[i];
  for(int k=1;k<=lg[tim];k++){
    
    for(int i=1;i+mi[k]-1<=tim;i++) mn[i][k]=cmp(mn[i][k-1],mn[i+mi[k-1]][k-1]);
  }
  return;
}
inline int Lca(int x,int y){
    
  int l=pos[x],r=pos[y];
  if(l>r) swap(l,r);
  int k=lg[r-l+1];
  //printf(" x=%d y=%d (%d %d) Lca=%d\n",x,y,pos[x],pos[y],cmp(mn[l][k],mn[r-mi[k]+1][k]));
  return cmp(mn[l][k],mn[r-mi[k]+1][k]);
}
inline ll Dis(int x,int y){
    
  return dis[x]+dis[y]-2*dis[Lca(x,y)];
}
struct pt{
    
  int id;
  ll w;
};
inline ll calc(const pt &a,const pt &b){
      
  return Dis(a.id,b.id)+a.w+b.w;
}
int id[N],ed[N],rku[N],rkv[N];

struct node{
    
  pt x,y;
};
inline void print(const node &a,int op=1){
    
  printf("[ (%d %lld) (%d %lld) ] %c",a.x.id,a.x.w,a.y.id,a.y.w,op?'\n':' ');
}
inline ll getans(const node &a,const node &b){
    
  ll q=calc(a.x,b.x),w=calc(a.x,b.y),e=calc(a.y,b.x),r=calc(a.y,b.y),mx=max({
    q,w,e,r});
  return mx;
}
inline node merge(const node &a,const node &b){
    
  ll q=calc(a.x,b.x),w=calc(a.x,b.y),e=calc(a.y,b.x),r=calc(a.y,b.y),t=calc(a.x,a.y),y=calc(b.x,b.y),mx=max({
    q,w,e,r,t,y});
  if(mx==q) return (node){
    a.x,b.x};
  if(mx==w) return (node){
    a.x,b.y};
  if(mx==e) return (node){
    a.y,b.x};
  if(mx==r) return (node){
    a.y,b.y};
  if(mx==t) return (node){
    a.x,a.y};
  if(mx==y) return (node){
    b.x,b.y};
  assert(0);
}

struct tree{
    
  int ls,rs;
  node o;
}tr[N*30];
int rt[N],tot;
inline void pushup(int k){
    
  tr[k].o=merge(tr[tr[k].ls].o,tr[tr[k].rs].o);
  /*printf("merge: "); print(tr[tr[k].ls].o,0); print(tr[tr[k].rs].o,0); print(tr[k].o,1);*/
  return;
}
#define mid ((l+r)>>1)
inline int New(){
    
  tr[++tot]=tr[0];
  return tot;
}
void upd(int &k,int l,int r,int p,ll w,int op){
    
  if(!k) k=New();
  if(l==r){
    
    assert(id[l]);
    if(op==1) tr[k].o.x=(pt){
    id[l],w};
    else tr[k].o.x=(pt){
    id[l],-inf};
    return;
  }
  if(p<=mid) upd(tr[k].ls,l,mid,p,w,op);
  else upd(tr[k].rs,mid+1,r,p,w,op);
  pushup(k);
  return;
}
int merge(int x,int y){
    
  if(!x||!y) return x|y;
  int now=++tot;
  tr[now].ls=merge(tr[x].ls,tr[y].ls);
  tr[now].rs=merge(tr[x].rs,tr[y].rs);
  pushup(now);
  return now;
}

struct ope{
    
  int op,p;
  ll w;
};
vector<ope>ve[N];

int u[N],v[N];
ll c[N];
int S;
ll ans;

void solve(int x,int f){
    
  for(int i=fi[x];~i;i=p[i].nxt){
    
    int to=p[i].to;
    if(to==f) continue;
    solve(to,x);
  }
  if(Flag) printf("solve: x=%d\n",x);
  for(ope o:ve[x]){
        
    if(o.op==1){
    
      
      pt ww=(pt){
    id[o.p],o.w};
      ans=max(ans,calc(ww,tr[rt[x]].o.x)-2*dis[x]);
      ans=max(ans,calc(ww,tr[rt[x]].o.y)-2*dis[x]);
      
      upd(rt[x],1,S,o.p,o.w,o.op);

      if(Flag) printf(" ins: p=%d x=%d\n",o.p,id[o.p]);      
    }
  }
  for(int i=fi[x];~i;i=p[i].nxt){
    
    int to=p[i].to;
    if(to==f) continue;
    ll o=getans(tr[rt[x]].o,tr[rt[to]].o)-2*dis[x];
    if(Flag) if(o>ans){
    
      printf("%d -> %d o=%lld ",x,to,o);
      print(tr[rt[x]].o,0);
      print(tr[rt[to]].o,1);
    }
    ans=max(ans,o);
    rt[x]=merge(rt[x],rt[to]);
  }
  for(ope o:ve[x]){
        
    if(o.op==-1){
    
      upd(rt[x],1,S,o.p,o.w,o.op);
      if(Flag) printf(" del: p=%d x=%d\n",o.p,id[o.p]);
    }
  }
  return;
}

void init(){
    
  tim=0;
  cnt=-1;
  tot=0;
  ans=-inf;
  tr[0].o.x=tr[0].o.y=(pt){
    1,-inf};
  for(int i=1;i<=n;i++){
    
    fi[i]=-1;
    memset(pl[i],0,sizeof(pl[i]));
    ed[i]=0;
    rt[i]=0;
    ve[i].clear();
  }
}

void work(){
    
  n=read();
  init();
  for(int i=1;i<n;i++){
    
    int x=read(),y=read(),w=read();
    addline(x,y,w);
    addline(y,x,w);
  }
  dfs(1,0);
  ST();
  m=read();
  for(int i=1;i<=m;i++){
    
    u[i]=read();v[i]=read();
    c[i]=Dis(u[i],v[i])-read()*2;
    rku[i]=++ed[u[i]];rkv[i]=++ed[v[i]];
  }
  for(int i=1;i<=n;i++){
    
    ed[i]+=ed[i-1];
    for(int j=ed[i-1]+1;j<=ed[i];j++) id[j]=i;
  }
  S=ed[n];
  for(int i=1;i<=m;i++){
    
    int anc=Lca(u[i],v[i]);
    if(anc!=u[i]){
    
      int p=jump(u[i],anc);
      ve[u[i]].push_back((ope){
    1,ed[v[i]-1]+rkv[i],c[i]+dis[u[i]]});
      ve[p].push_back((ope){
    -1,ed[v[i]-1]+rkv[i],c[i]+dis[u[i]]});
    }
    if(anc!=v[i]){
    
      int p=jump(v[i],anc);
      ve[v[i]].push_back((ope){
    1,ed[u[i]-1]+rku[i],c[i]+dis[v[i]]});
      ve[p].push_back((ope){
    -1,ed[u[i]-1]+rku[i],c[i]+dis[v[i]]});
    }
  }
  solve(1,0);
  if(ans<-1e18) puts("F");
  else printf("%lld\n",ans>>1);
}

bool mem2;
signed main(){
    

  #ifndef ONLINE_JUDGE
  freopen("a.in","r",stdin);
  freopen("a.out","w",stdout);
  #endif
  debug("mem=%.2lf\n",abs(&mem2-&mem1)/1024./1024);

  int T=read();
  while(T--){
    
    //if(T%100==0) debug("%d\n",T);
    work();
  }
  return 0;
}