QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#695491 | #5439. Meet in the Middle | larryyu | WA | 3ms | 19980kb | C++20 | 3.9kb | 2024-10-31 20:08:39 | 2024-10-31 20:08:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ls x<<1
#define rs x<<1|1
int t,n,q,cnt1,cnt2;
int dep[100010],id[200020],val[200020],fi[100010],st[200020][20];
int dis[100010],dfn[100010],siz[100010],no[100010],ans[500050];
vector<pii> v[100010];
struct tre{
int tot;
int head[100010];
struct edge{
int to,next,w;
}e[200020];
void add(int x,int y,int z){
e[++tot]=edge{y,head[x],z};
head[x]=tot;
}
void init(){
for(int i=1;i<=n;i++) head[i]=0;
tot=0;
}
}t1,t2;
int getl(int l,int r){
if(r<l) swap(l,r);
int len=log2(r-l+1);
int x=st[l][len],y=st[r-(1<<len)+1][len];
if(val[x]<val[y]) return id[x];
return id[y];
}
int calc(int x,int y){
int lca=getl(fi[x],fi[y]);
return dep[x]+dep[y]-2*dep[lca];
}
struct tree{
int x,y,adx,ady,tag;
friend tree operator+(tree a,tree b){
tree c;
int v1=calc(a.x,a.y)+a.adx+a.ady;
int v2=calc(b.x,b.y)+b.adx+b.ady;
int v3=calc(a.x,b.y)+a.adx+b.ady;
int v4=calc(a.y,b.x)+a.ady+b.adx;
int v5=calc(a.x,b.x)+a.adx+b.adx;
int v6=calc(a.y,b.y)+a.ady+b.ady;
int val=max(max(v1,max(v2,v3)),max(v4,max(v5,v6)));
if(val==v1){
c=tree{a.x,a.y,a.adx,a.ady,0};
}else if(val==v2){
c=tree{b.x,b.y,b.adx,b.ady,0};
}else if(val==v3){
c=tree{a.x,b.y,a.adx,b.ady,0};
}else if(val==v4){
c=tree{a.y,b.x,a.ady,b.adx,0};
}else if(val==v5){
c=tree{a.x,b.x,a.adx,b.adx,0};
}else {
c=tree{a.y,b.y,a.ady,b.ady,0};
}
return c;
}
}tr[400040];
void lazy(int x,int v){
tr[x].tag+=v;
tr[x].adx+=v,tr[x].ady+=v;
}
void pushdown(int x){
if(!tr[x].tag) return ;
lazy(ls,tr[x].tag);
lazy(rs,tr[x].tag);
tr[x].tag=0;
}
void build(int x,int l,int r){
if(l==r){
tr[x]=tree{no[l],no[r],dis[no[l]],dis[no[r]],0};
return ;
}
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
tr[x]=tr[ls]+tr[rs];
}
void update(int x,int l,int r,int L,int R,int v){
if(l>=L&&r<=R) return lazy(x,v),void();
pushdown(x);
int mid=l+r>>1;
if(L<=mid) update(ls,l,mid,L,R,v);
if(R>=mid+1) update(rs,mid+1,r,L,R,v);
tr[x]=tr[ls]+tr[rs];
}
void dfs1(int x,int fax){
fi[x]=++cnt1;
id[cnt1]=x,val[cnt1]=dep[x];
for(int i=t2.head[x];i;i=t2.e[i].next){
int y=t2.e[i].to,w=t2.e[i].w;
if(y==fax) continue;
dep[y]=dep[x]+w;
dfs1(y,x);
id[++cnt1]=x,val[cnt1]=dep[x];
}
}
void dfs2(int x,int fax){
dfn[x]=++cnt2,no[cnt2]=x;
siz[x]=1;
for(int i=t1.head[x];i;i=t1.e[i].next){
int y=t1.e[i].to,w=t1.e[i].w;
if(y==fax) continue;
dis[y]=dis[x]+w;
dfs2(y,x);
siz[x]+=siz[y];
}
}
void dfs3(int x,int fax){
for(auto i:v[x]){
int x=tr[1].x,y=tr[1].y,dx=tr[1].adx,dy=tr[1].ady;
int lx=calc(i.first,x)+dx,ly=calc(i.first,y)+dy;
if(lx>ly) ans[i.second]=lx;
else ans[i.second]=ly;
}
for(int i=t1.head[x];i;i=t1.e[i].next){
int y=t1.e[i].to,w=t1.e[i].w;
if(y==fax) continue;
update(1,1,n,1,n,w);
update(1,1,n,dfn[y],dfn[y]+siz[y]-1,-2*w);
dfs3(y,x);
update(1,1,n,1,n,-w);
update(1,1,n,dfn[y],dfn[y]+siz[y]-1,2*w);
}
}
void init(){
t1.init(),t2.init();
cnt1=0,cnt2=0;
for(int i=1;i<=n;i++) v[i].clear();
}
void solve(){
init();
cin>>n;
for(int i=1;i<n;i++){
int x,y,z;
cin>>x>>y>>z;
t1.add(x,y,z),t1.add(y,x,z);
}
for(int i=1;i<n;i++){
int x,y,z;
cin>>x>>y>>z;
t2.add(x,y,z),t2.add(y,x,z);
}
cin>>q;
for(int i=1;i<=q;i++){
int x,y;
cin>>x>>y;
v[x].push_back({y,i});
}
dfs1(1,0);
for(int i=1;i<=cnt1;i++){
st[i][0]=i;
}
for(int j=1;j<=18;j++){
for(int i=1;i+(1<<j)-1<=cnt1;i++){
int x=st[i][j-1],y=st[i+(1<<j-1)][j-1];
if(val[x]<val[y]){
st[i][j]=x;
}else st[i][j]=y;
}
}
dfs2(1,0);
build(1,1,n);
dfs3(1,0);
for(int i=1;i<=q;i++){
cout<<ans[i]<<'\n';
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(nullptr);
// cin>>t;
// while(t--){
solve();
// }
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 19980kb
input:
3 4 1 2 1 2 3 2 1 2 2 2 3 1 1 1 1 2 2 1 2 2
output:
5
result:
wrong answer 1st numbers differ - expected: '6', found: '5'