题解 P6157 【有趣的游戏】

Alex_Wei · 2020-03-01 22:09:23 · 题解

题面传送门

感觉比 D 简单一点 （因为我对数论一窍不通）。

首先明确一点，选出的 w_x 一定是第二大的，w_y 一定是最大的，此时 w_x\bmod w_y 最大。

• 为什么？不妨设 w_x<w_y，那么 w_x\bmod w_y=w_x，而 w_y\bmod w_x 一定小于 w_x，所以选出的 w_x,w_y 满足 w_x<w_y。

  因此，要使 w_x\bmod w_y 最大，w_x 一定是第二大的，w_y 一定是最大的。

这样问题就被我们转化成了：

• 给定一条链，设 x 为该链上权值严格第二大的节点，y 为该链上权值最大的节点，求出 w_x。这可以用树剖和线段树维护。

• 求出去掉 x,y 后剩余的点中严格第二大的权值。这可以用一个 multiset 维护。

其实，如果不带修，这道题目还能用主席树来做，可惜主席树无法支持这样的修改。

#include<bits/stdc++.h>
using namespace std;
char buf[1<<23],*p1=buf,*p2=buf;
inline int read(){
    int x=0,sign=0; char s=getchar();
    while(!isdigit(s))sign|=s=='-',s=getchar();
    while(isdigit(s))x=(x<<1)+(x<<3)+(s-'0'),s=getchar();
    return sign?-x:x;
}
const int N=1e5+5;
int ct,hd[N],nxt[N<<1],vv[N<<1];
inline void add(int u,int v){
    nxt[++ct]=hd[u],hd[u]=ct,vv[ct]=v;
}
int n,q,dnum,fa[N],dep[N],siz[N],son[N],ind[N],top[N],rk[N];
void dfs1(int id,int f,int d){
    fa[id]=f,siz[id]=1,dep[id]=d;
    for(int i=hd[id];i;i=nxt[i]){
        int to=vv[i];
        if(to!=f){
            dfs1(to,id,d+1);
            if(siz[son[id]]<siz[to])son[id]=to;
            siz[id]+=siz[to];
        }
    }
}
void dfs2(int id,int t){
    top[id]=t,ind[id]=++dnum,rk[dnum]=id;
    if(!son[id])return;
    dfs2(son[id],t);
    for(int i=hd[id];i;i=nxt[i]){
        int to=vv[i];
        if(to!=fa[id]&&to!=son[id])dfs2(to,to);
    }
}
multiset <int> s;
int val[N];
struct data{
    int fi,se;
}c[N<<2];
data mer(data a,data b){
    int fi=max(a.fi,b.fi);//维护最大/第二大值
    return {fi,max(a.fi==fi?a.se:a.fi,b.fi==fi?b.se:b.fi)}; 
}
void build(int l,int r,int x){
    if(l==r){
        c[x]={val[rk[l]],-1};
        return;
    }
    int m=l+r>>1;
    build(l,m,x<<1),build(m+1,r,x<<1|1);
    c[x]=mer(c[x<<1],c[x<<1|1]);
}
void modify(int l,int r,int x,int pos,int v){
    if(l==r){
        val[rk[l]]+=v;
        c[x]={val[rk[l]],-1};
        return;
    }
    int m=l+r>>1;
    if(pos<=m)modify(l,m,x<<1,pos,v);
    else modify(m+1,r,x<<1|1,pos,v);
    c[x]=mer(c[x<<1],c[x<<1|1]);
}
data query(int l,int r,int ql,int qr,int x){
    if(ql<=l&&r<=qr)return c[x];
    int m=l+r>>1; data ans={-1,-1};
    if(ql<=m)ans=mer(ans,query(l,m,ql,qr,x<<1));
    if(m<qr)ans=mer(ans,query(m+1,r,ql,qr,x<<1|1));
    return ans;
}
data query(int x,int y){
    data ans={-1,-1};
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        ans=mer(ans,query(1,n,ind[top[x]],ind[x],1));
        x=fa[top[x]];
    }
    if(ind[x]>ind[y])swap(x,y);
    return mer(ans,query(1,n,ind[x],ind[y],1));
}
int main(){
    n=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        add(u,v),add(v,u);
    }
    dfs1(1,0,0),dfs2(1,1);
    for(int i=1;i<=n;i++)val[i]=read(),s.insert(val[i]);
    build(1,n,1);
    q=read();
    for(int i=0;i<q;i++){
        int op=read(),x=read(),y=read();
        if(op){
            data t=query(x,y);
            if(t.se==-1){
                puts("-1");
                continue;
            }
            printf("%d ",t.se);
            s.erase(s.find(t.fi)),s.erase(s.find(t.se));
            printf("%d\n",*(--s.lower_bound(*--s.end())));
            s.insert(t.fi),s.insert(t.se);
        }
        else{
            s.erase(s.find(val[x])),s.insert(val[x]+y);
            modify(1,n,1,ind[x],y);
        }
    }
    return 0;
}