QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#308135 | #5439. Meet in the Middle | xx019 | TL | 0ms | 0kb | C++20 | 4.1kb | 2024-01-19 16:27:58 | 2024-01-19 16:27:58 |
answer
#include<bits/stdc++.h>
#define int long long
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
const int inf=1e18,mod=998244353;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
struct edge{
int v,w,nxt;
};
struct Graph{
int tot,head[100005];edge e[200005];
void add(int u,int v,int w){
e[++tot]=(edge){v,w,head[u]},head[u]=tot;
}
int cur,dfn[100005],rnk[100005],d[100005],f[22][100005],siz[100005];
int getmin(int x,int y){
return ((dfn[x]<dfn[y])?x:y);
}
void dfs(int u,int fa){
dfn[u]=++cur,rnk[cur]=u,f[0][cur]=fa;siz[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;if(v==fa)continue;
d[v]=d[u]+w;dfs(v,u);siz[u]+=siz[v];
}
}
int getlca(int u,int v){
if(u==v)return u;
if((u=dfn[u])>(v=dfn[v]))swap(u,v);
int o=__lg(v-u++);
return getmin(f[o][u],f[o][v-(1ll<<o)+1]);
}
void init(){
dfs(1,0);
for(int j=1;(1ll<<j)<=cur;j++){
for(int i=1;i+(1ll<<j)-1<=cur;i++){
f[j][i]=getmin(f[j-1][i],f[j-1][i+(1ll<<(j-1))]);
}
}
}
int dist(int u,int v){
return d[u]+d[v]-d[getlca(u,v)]*2;
}
}t1,t2;
struct Chain{
int u,v,du,dv,d;
Chain(const int &_u=0,const int &_v=0,const int &_du=0,const int &_dv=0,const int &_d=0):u(_u),v(_v),du(_du),dv(_dv),d(_du+_dv+_d){}
bool operator <(const Chain &b)const{
return d<b.d;
}
Chain operator +(const Chain &b)const{
Chain c=max(*this,b);
if(u&&b.u)c=max(c,Chain(u,b.u,du,b.du,t1.dist(u,b.u)));
if(u&&b.v)c=max(c,Chain(u,b.v,du,b.dv,t1.dist(u,b.v)));
if(v&&b.u)c=max(c,Chain(v,b.u,dv,b.du,t1.dist(v,b.u)));
if(v&&b.v)c=max(c,Chain(v,b.v,dv,b.dv,t1.dist(v,b.v)));
return c;
}
};
struct segtree{
#define ls (p<<1)
#define rs (p<<1|1)
#define lson l,mid,ls
#define rson mid+1,r,rs
Chain c[400005];int tag[400005];
void pushup(int p){
c[p]=c[ls]+c[rs];
}
void pushdown(int p){
tag[ls]+=tag[p],tag[rs]+=tag[p];
if(c[ls].u)c[ls].du+=tag[p];
if(c[ls].v)c[ls].dv+=tag[p];
if(c[ls].u&&c[ls].v)c[ls].d+=2*tag[p];
if(c[rs].u)c[rs].du+=tag[p];
if(c[rs].v)c[rs].dv+=tag[p];
if(c[rs].u&&c[rs].v)c[rs].d+=2*tag[p];
tag[p]=0;
}
void build(int l,int r,int p){
tag[p]=0;
if(l==r){
c[p]=Chain(t1.rnk[l],0,t1.d[t1.rnk[l]],0,0);
return;
}
int mid=(l+r)>>1;
build(lson);build(rson);
pushup(p);
}
void add(int l,int r,int p,int L,int R,int v){
if(L>R)return;
if(L<=l&&r<=R){
tag[p]+=v;
if(c[p].u)c[p].du+=v;
if(c[p].v)c[p].dv+=v;
if(c[p].u&&c[p].v)c[p].d+=2*v;
return;
}
int mid=(l+r)>>1;pushdown(p);
if(L<=mid)add(lson,L,R,v);
if(R>mid)add(rson,L,R,v);
pushup(p);
}
Chain ask(int l,int r,int p,int L,int R){
if(L<=l&&r<=R)return c[p];
int mid=(l+r)>>1;pushdown(p);
if(R<=mid)return ask(lson,L,R);
if(L>mid)return ask(rson,L,R);
return ask(lson,L,R)+ask(rson,L,R);
}
#undef lson
#undef rson
#undef ld
#undef rs
}Tr;
int T,n,q,qu[500005],qv[500005],ans[500005];vector<int>t[100005];
void solve(int u,int fa){
Chain l=Tr.ask(1,n,1,1,n);
for(auto x:t[u]){
if(l.u)ans[x]=max(ans[x],t1.dist(qu[x],l.u)+t2.dist(l.u,qv[x]));
if(l.v)ans[x]=max(ans[x],t1.dist(qu[x],l.v)+t2.dist(l.v,qv[x]));
}
for(int i=t2.head[u];i;i=t2.e[i].nxt){
int v=t2.e[i].v,w=t2.e[i].w;if(v==fa)continue;
Tr.add(1,n,1,t2.dfn[v],t2.dfn[v]+t2.siz[v]-1,-w);
Tr.add(1,n,1,1,t2.dfn[v]-1,w);
Tr.add(1,n,1,t2.dfn[v]+t2.siz[v],n,w);
solve(v,u);
Tr.add(1,n,1,t2.dfn[v],t2.dfn[v]+t2.siz[v]-1,w);
Tr.add(1,n,1,1,t2.dfn[v]-1,-w);
Tr.add(1,n,1,t2.dfn[v]+t2.siz[v],n,-w);
}
}
signed main(){
T=read(),n=read(),q=read();
for(int i=1,u,v,w;i<n;i++)u=read(),v=read(),w=read(),t1.add(u,v,w),t1.add(v,u,w);
for(int i=1,u,v,w;i<n;i++)u=read(),v=read(),w=read(),t2.add(u,v,w),t2.add(v,u,w);
t1.init();t2.init();Tr.build(1,n,1);
for(int i=1;i<=q;i++)qu[i]=read(),qv[i]=read(),t[qv[i]].push_back(i);
solve(1,0);for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
3 4 1 2 1 2 3 2 1 2 2 2 3 1 1 1 1 2 2 1 2 2