QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#695400#5439. Meet in the MiddleY204335WA 0ms42556kbC++144.4kb2024-10-31 19:57:332024-10-31 19:57:36

Judging History

你现在查看的是最新测评结果

  • [2024-10-31 19:57:36]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:42556kb
  • [2024-10-31 19:57:33]
  • 提交

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'