QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#693648 | #5439. Meet in the Middle | dyj133446 | WA | 0ms | 22028kb | C++14 | 3.2kb | 2024-10-31 16:31:07 | 2024-10-31 16:31:25 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+5;
int T,n,q,st[2][17][N],dfn[2][N],sz[2][N],w[2][N],tot;
ll dis[2][N],ans[5*N],tag[4*N],Tag;
vector<pair<int,int>>e[2][N],Q[N];
struct node{
int x[2];
ll val[2];
}tree[4*N];
int Get(int op,int x,int y)
{
if(dfn[op][x]<dfn[op][y])return x;
return y;
}
void dfs(int op,int x,int prt)
{
dfn[op][x]=++tot;w[op][tot]=x,st[op][0][tot]=prt,sz[op][x]=1;
for(auto y:e[op][x])if(y.first!=prt)
{
dis[op][y.first]=dis[op][x]+y.second,dfs(op,y.first,x),sz[op][x]+=sz[op][y.first];
}
}
int lca(int op,int x,int y)
{
if(x==y)return x;
x=dfn[op][x],y=dfn[op][y];
if(x>y)swap(x,y);
int k=__lg(y-x);
return Get(op,st[op][k][x+1],st[op][k][y-(1<<k)+1]);
}
ll getdis(int op,int x,int y)
{
return dis[op][x]+dis[op][y]-2*dis[op][lca(op,x,y)];
}
void pushdown(int x)
{
if(tag[x])
{
tag[x<<1]+=tag[x],tag[x<<1|1]+=tag[x];
tree[x<<1].val[0]+=tag[x],tree[x<<1].val[1]+=tag[x];
tree[x<<1|1].val[0]+=tag[x],tree[x<<1|1].val[1]+=tag[x];
tag[x]=0;
}
}
void pushup(int x)
{
ll maxx=-1e18;
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
ll xx=tree[x<<1].val[i]+tree[x<<1|1].val[j]+getdis(1,tree[x<<1].x[i],tree[x<<1|1].x[j]);
if(xx>maxx)
{
maxx=xx,tree[x].x[0]=tree[x<<1].x[i],tree[x].x[1]=tree[x<<1|1].x[j];
tree[x].val[0]=tree[x<<1].val[i],tree[x].val[1]=tree[x<<1|1].val[j];
}
}
}
for(int o=0;o<2;o++)
{
ll xx=tree[x<<1|o].val[0]+tree[x<<1|o].val[1]+getdis(1,tree[x<<1|o].x[0],tree[x<<1|o].x[1]);
if(xx>maxx)maxx=xx,tree[x]=tree[x<<1|o];
}
}
void build(int x,int l,int r)
{
tag[x]=0;
if(l==r)return tree[x].x[0]=tree[x].x[1]=w[0][l],tree[x].val[0]=tree[x].val[1]=getdis(0,1,w[0][l]),void();
int mid=(l+r)/2;
build(x<<1,l,mid),build(x<<1|1,mid+1,r);
pushup(x);
}
void change(int x,int L,int R,int l,int r,ll t)
{
if(l>r)return;
if(L>=l&&R<=r)return tag[x]+=t,tree[x].val[0]+=t,tree[x].val[1]+=t,void();
pushdown(x);
int mid=(L+R)/2;
if(l<=mid)change(x<<1,L,mid,l,r,t);
if(r>mid)change(x<<1|1,mid+1,R,l,r,t);
pushup(x);
}
void DFS(int x,int prt)
{
for(auto y:Q[x])ans[y.second]=max(getdis(1,y.first,tree[1].x[0])+tree[1].val[0]+Tag,getdis(1,y.first,tree[1].x[1])+tree[1].val[1]+Tag);
for(auto y:e[0][x])if(y.first!=prt)
{
Tag+=y.second;
change(1,1,n,dfn[0][y.first],dfn[0][y.first]+sz[0][y.first]-1,-2ll*y.second);
DFS(y.first,x);
Tag-=y.second;
change(1,1,n,dfn[0][y.first],dfn[0][y.first]+sz[0][y.first]-1,2ll*y.second);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
T=1;
while(T--)
{
cin>>n,Tag=0;
for(int i=1;i<=n;i++)e[0][i].clear(),e[1][i].clear(),Q[i].clear();
for(int i=0;i<2;i++)
{
for(int j=1;j<n;j++)
{
int x,y,z;
cin>>x>>y>>z;
e[i][x].emplace_back(y,z),e[i][y].emplace_back(x,z);
}
tot=0,dfs(i,1,0);
}
for(int i=0;i<2;i++)
{
for(int j=1;j<17;j++)
{
for(int k=1;k+(1<<j)-1<=n;k++)st[i][j][k]=Get(i,st[i][j-1][k],st[i][j-1][k+(1<<(j-1))]);
}
}
cin>>q;
for(int i=1;i<=q;i++)
{
int x,y;
cin>>x>>y,ans[i]=0,Q[x].emplace_back(y,i);
}
build(1,1,n),DFS(1,0);
for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 22028kb
input:
3 4 1 2 1 2 3 2 1 2 2 2 3 1 1 1 1 2 2 1 2 2
output:
12
result:
wrong answer 1st numbers differ - expected: '6', found: '12'