做网站如何注意排版问题,装修家具,外链,网站存在的问题及改进措施前言
似乎也没有那么难#xff1f; 但确实也不太好想。
解析
对于两条有交路径 (u1,v1,c1),(u2,v2,c2)(u_1,v_1,c_1),(u_2,v_2,c_2)(u1,v1,c1),(u2,v2,c2)#xff0c;设 tlca(u1,u1)tlca(u_1,u_1)tlca(u1,u1) 为四个 lca 中最深的#xff0c;那么代价的二…前言
似乎也没有那么难 但确实也不太好想。
解析
对于两条有交路径 (u1,v1,c1),(u2,v2,c2)(u_1,v_1,c_1),(u_2,v_2,c_2)(u1,v1,c1),(u2,v2,c2)设 tlca(u1,u1)tlca(u_1,u_1)tlca(u1,u1) 为四个 lca 中最深的那么代价的二倍可以写为 dis(u1,v1)dis(u2,v2)dis(u1,u2)dis(v1,v2)−2c1−2c2dis(u_1,v_1)dis(u_2,v_2)dis(u_1,u_2)dis(v_1,v_2)-2c_1-2c_2dis(u1,v1)dis(u2,v2)dis(u1,u2)dis(v1,v2)−2c1−2c2。 枚举 ttt 的位置距离可以写成 dis(u1,v1)depu1−2c1dis(u2,v2)depu2−2c2dis(v1,v2)−2deptdis(u_1,v_1)dep_{u_1}-2c_1dis(u_2,v_2)dep_{u_2}-2c_2dis(v_1,v_2)-2dep_tdis(u1,v1)depu1−2c1dis(u2,v2)depu2−2c2dis(v1,v2)−2dept可以看成 dis(v1,v2)w1w2−2deptdis(v_1,v_2)w_1w_2-2dep_tdis(v1,v2)w1w2−2dept 的形式。 看到最大距离容易想到线段树维护直径的经典做法。 可以看成新的“ v1v_1v1” 是原来的点连出一条长度为 w1w_1w1 的边所以依然可以刻画为树的结构虽然有负权边但是由于负权边必然有一个端点是叶子所以原来的结论还是对的。
每个节点维护子树内“v”节点集合合并时先更新答案再线段树合并即可时空复杂度 O(mlogmnlogn)O(m\log mn\log n)O(mlogmnlogn)。
记得要再到达 lca 之前把点删掉。
代码
#includebits/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 cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}
bool mem1;const int N2e5100;
const ll inf2e18;
const int mod998244353;
const bool Flag0;#define add(x,y) ((((x)(y))mod)((x)-mod))
inline ll ksm(ll x,ll k){ll res(1);while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}int n,m;struct edge{int to,nxt,w;
}p[N1];
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 k16;k0;k--){if(dep[pl[x][k]]dep[anc]) continue;xpl[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 k1;pl[x][k-1];k) pl[x][k]pl[pl[x][k-1]][k-1];for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof) 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 i1;itim;i) lg[i]lg[i1]1;mi[0]1;for(int i1;ilg[tim];i) mi[i]mi[i-1]1;for(int i1;itim;i) mn[i][0]q[i];for(int k1;klg[tim];k){for(int i1;imi[k]-1tim;i) mn[i][k]cmp(mn[i][k-1],mn[imi[k-1]][k-1]);}return;
}
inline int Lca(int x,int y){int lpos[x],rpos[y];if(lr) swap(l,r);int klg[r-l1];//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.wb.w;
}
int id[N],ed[N],rku[N],rkv[N];struct node{pt x,y;
};
inline void print(const node a,int op1){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 qcalc(a.x,b.x),wcalc(a.x,b.y),ecalc(a.y,b.x),rcalc(a.y,b.y),mxmax({q,w,e,r});return mx;
}
inline node merge(const node a,const node b){ll qcalc(a.x,b.x),wcalc(a.x,b.y),ecalc(a.y,b.x),rcalc(a.y,b.y),tcalc(a.x,a.y),ycalc(b.x,b.y),mxmax({q,w,e,r,t,y});if(mxq) return (node){a.x,b.x};if(mxw) return (node){a.x,b.y};if(mxe) return (node){a.y,b.x};if(mxr) return (node){a.y,b.y};if(mxt) return (node){a.x,a.y};if(mxy) 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].omerge(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 ((lr)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) kNew();if(lr){assert(id[l]);if(op1) tr[k].o.x(pt){id[l],w};else tr[k].o.x(pt){id[l],-inf};return;}if(pmid) upd(tr[k].ls,l,mid,p,w,op);else upd(tr[k].rs,mid1,r,p,w,op);pushup(k);return;
}
int merge(int x,int y){if(!x||!y) return x|y;int nowtot;tr[now].lsmerge(tr[x].ls,tr[y].ls);tr[now].rsmerge(tr[x].rs,tr[y].rs);pushup(now);return now;
}struct ope{int op,p;ll w;
};
vectoropeve[N];int u[N],v[N];
ll c[N];
int S;
ll ans;void solve(int x,int f){for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof) continue;solve(to,x);}if(Flag) printf(solve: x%d\n,x);for(ope o:ve[x]){ if(o.op1){pt ww(pt){id[o.p],o.w};ansmax(ans,calc(ww,tr[rt[x]].o.x)-2*dis[x]);ansmax(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 ifi[x];~i;ip[i].nxt){int top[i].to;if(tof) continue;ll ogetans(tr[rt[x]].o,tr[rt[to]].o)-2*dis[x];if(Flag) if(oans){printf(%d - %d o%lld ,x,to,o);print(tr[rt[x]].o,0);print(tr[rt[to]].o,1);}ansmax(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(){tim0;cnt-1;tot0;ans-inf;tr[0].o.xtr[0].o.y(pt){1,-inf};for(int i1;in;i){fi[i]-1;memset(pl[i],0,sizeof(pl[i]));ed[i]0;rt[i]0;ve[i].clear();}
}void work(){nread();init();for(int i1;in;i){int xread(),yread(),wread();addline(x,y,w);addline(y,x,w);}dfs(1,0);ST();mread();for(int i1;im;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 i1;in;i){ed[i]ed[i-1];for(int jed[i-1]1;jed[i];j) id[j]i;}Sed[n];for(int i1;im;i){int ancLca(u[i],v[i]);if(anc!u[i]){int pjump(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 pjump(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,ans1);
}bool mem2;
signed main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifdebug(mem%.2lf\n,abs(mem2-mem1)/1024./1024);int Tread();while(T--){//if(T%1000) debug(%d\n,T);work();}return 0;
}
