QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#695400 | #5439. Meet in the Middle | Y204335 | WA | 0ms | 42556kb | C++14 | 4.4kb | 2024-10-31 19:57:33 | 2024-10-31 19:57:36 |
Judging History
answer
#include<bits/stdc++.h>
#define lli long long
#define fir first
#define sec second
using namespace std;
const int N=1e5+10,L=20,Q=5e5+10;
int n,q,dfn[2][N],fdfn[N],st[L][N],tot,lg[N],siz[N];
lli val[2][N],ans[Q];
vector<pair<int,lli>>e[2][N];
vector<pair<int,int>>x[Q];
int lca(int a,int b){
if(a==b)return a;
a=dfn[1][a];b=dfn[1][b];
if(a>b)swap(a,b);
if(dfn[1][st[lg[b-a]][a+1]]<dfn[1][st[lg[b-a]][b-(1<<lg[b-a])+1]]){
return st[lg[b-a]][a+1];
}
else{
return st[lg[b-a]][b-(1<<lg[b-a])+1];
}
}
struct info{
int a,b;
lli vala,valb;
info(){
a=b=vala=valb=0;
}
};
struct sgtr{
info tr[N<<2];
lli tag[N<<2];
void check(info& a,int x,int y,lli valx,lli valy,lli& valn){
lli temp=val[1][x]+val[1][y]-2*val[1][lca(x,y)]+valx+valy;
if(temp>valn){
a.a=x;
a.b=y;
a.vala=valx;
a.valb=valy;
valn=temp;
}
}
info calc(info a,info b){
info res;
lli val=0;
check(res,a.a,a.b,a.vala,a.valb,val);
check(res,a.a,b.a,a.vala,b.vala,val);
check(res,a.a,b.b,a.vala,b.valb,val);
check(res,a.b,b.a,a.valb,b.vala,val);
check(res,a.b,b.b,a.valb,b.valb,val);
check(res,b.a,b.b,b.vala,b.valb,val);
return res;
}
void up(int p){
tr[p]=calc(tr[p<<1],tr[(p<<1)+1]);
}
void build(int l,int r,int p){
tag[p]=0;
if(l==r){
tr[p].a=tr[p].b=fdfn[l];
tr[p].vala=tr[p].valb=val[0][fdfn[l]];
return;
}
int mid=(l+r)>>1;
build(l,mid,p<<1);
build(mid+1,r,(p<<1)+1);
up(p);
}
info quary(){
return tr[1];
}
void change(lli w,int p){
tr[p].vala+=w;
tr[p].valb+=w;
tag[p]+=w;
}
void down(int p){
if(!tag[p])return;
change(tag[p],p<<1);
change(tag[p],(p<<1)+1);
tag[p]=0;
}
void updata(int l,int r,int ll,int rr,lli w,int p){
if(ll<=l&&r<=rr){
change(w,p);
return;
}
down(p);
int mid=(l+r)>>1;
if(ll<=mid)updata(l,mid,ll,rr,w,p<<1);
if(rr>=mid+1)updata(mid+1,r,ll,rr,w,(p<<1)+1);
up(p);
}
}tr;
void dfs(int p,int nw,int fa,lli w){
dfn[p][nw]=++tot;
val[p][nw]=w;
if(!p){
fdfn[dfn[p][nw]]=nw;
siz[nw]=1;
}
else{
st[0][dfn[p][nw]]=fa;
}
for(auto i:e[p][nw]){
if(i.fir==fa)continue;
dfs(p,i.fir,nw,w+i.sec);
if(!p)siz[nw]+=siz[i.fir];
}
}
void init(){
cin>>n;
tot=0;
for(int i=1;i<=n;i++){
e[0][i].clear();
e[1][i].clear();
x[i].clear();
}
for(int i=1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
e[0][u].push_back({v,w});
e[0][v].push_back({u,w});
}
for(int i=1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
e[1][u].push_back({v,w});
e[1][v].push_back({u,w});
}
cin>>q;
for(int i=1;i<=q;i++){
int a,b;
cin>>a>>b;
x[a].push_back({b,i});
}
tot=0;
dfs(0,1,0,0);
tot=0;
dfs(1,1,0,0);
for(int i=2;i<=n;i++){
lg[i]=lg[i/2]+1;
}
for(int i=1;i<=17;i++){
for(int j=1;j<=n;j++){
if(dfn[1][st[i-1][j]]<dfn[1][st[i-1][j+(1<<(i-1))]]){
st[i][j]=st[i-1][j];
}
else{
st[i][j]=st[i-1][j+(1<<(i-1))];
}
}
}
tr.build(1,n,1);
}
void solve(int nw,int fa){
for(auto i:x[nw]){
info temp=tr.quary();
ans[i.sec]=val[1][temp.a]+val[1][i.fir]-2*val[1][lca(temp.a,i.fir)]+temp.vala;
ans[i.sec]=max(ans[i.sec],val[1][temp.b]+val[1][i.fir]-2*val[1][lca(temp.b,i.fir)]+temp.valb);
}
for(auto i:e[0][nw]){
if(i.fir==fa)continue;
tr.updata(1,n,1,n,i.sec,1);
tr.updata(1,n,dfn[0][i.fir],dfn[0][i.fir]+siz[i.fir]-1,-i.sec*2,1);
solve(i.fir,nw);
tr.updata(1,n,1,n,-i.sec,1);
tr.updata(1,n,dfn[0][i.fir],dfn[0][i.fir]+siz[i.fir]-1,i.sec*2,1);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(nullptr);
init();
solve(1,0);
for(int i=1;i<=q;i++){
cout<<ans[i]<<'\n';
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 42556kb
input:
3 4 1 2 1 2 3 2 1 2 2 2 3 1 1 1 1 2 2 1 2 2
output:
9
result:
wrong answer 1st numbers differ - expected: '6', found: '9'