开始 2024-09-30 12:40:00

【2025省选前】20240930更正

结束 2025-09-06 00:00:00
Contest is over.
当前 2025-10-21 00:41:54

help for code
#include<bits/stdc++.h>
#define up(i,l,r) for(int i=(l);i<=(r);++i)
#define down(i,l,r) for(int i=(l);i>=(r);--i)
#define pi pair<int,int>
#define p1 first
#define p2 second
#define p_b push_back
#define m_p make_pair
using namespace std;
typedef long long ll;
inline ll read(){
    ll x=0;short t=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*t;
}
const int maxn=2e5+10;
int tim;vector<pair<pi,int> >vec[maxn];
void Ins(int l,int r,int k){
    vec[l].p_b(m_p(m_p(l,r),k));
    vec[r+1].p_b(m_p(m_p(l,r),-k));
}
struct ODT {
    set<pair<pi,int> >st;
    void ins(int x){
        auto it=st.lower_bound(m_p(m_p(x,x),0));
        pi S=m_p(x,x);
        if(it!=st.end()&&(*it).p1.p1==x+1){
            Ins((*it).p1.p1,(*it).p1.p2,tim-(*it).p2);S.p2=(*it).p1.p2;
            st.erase(*it);
        }it=st.lower_bound(m_p(m_p(x,x),0));
        if(it!=st.begin()){--it;
            if((*it).p1.p2==x-1){
                Ins((*it).p1.p1,(*it).p1.p2,tim-(*it).p2);S.p1=(*it).p1.p1;
                st.erase(*it);
            }
        }st.insert(m_p(S,tim));
    }void del(int x){
        auto it=st.lower_bound(m_p(m_p(x+1,0),0));
        --it;
        Ins((*it).p1.p1,(*it).p1.p2,tim-(*it).p2);
        auto jt=*it;st.erase(it);
        pi S1,S2;
        S1.p1=jt.p1.p1,S1.p2=x-1;
        S2.p1=x+1,S2.p2=jt.p1.p2;
        if(S1.p1<=S1.p2)st.insert(m_p(S1,tim));
        if(S2.p1<=S2.p2)st.insert(m_p(S2,tim));
    }void clear(){
        for(auto it:st)Ins(it.p1.p1,it.p1.p2,tim-it.p2);st.clear();
    }
}T[2];
int n,fa[maxn],dfn[maxn],siz[maxn],son[maxn],rnk[maxn],ct;
vector<int>v[maxn];
void dfs(int u){
    dfn[u]=++ct,siz[u]=1;rnk[ct]=u;
    for(int x:v[u])if(x!=fa[u]){
        fa[x]=u;dfs(x),siz[u]+=siz[x];
        if(siz[x]>siz[son[u]])son[u]=x;
    }
}
void Ins(int u){
    T[0].del(u),T[1].ins(u);
}
void ins(int u){
    up(i,dfn[u],dfn[u]+siz[u]-1)Ins(rnk[i]);
}
void dfs2(int u){
    for(int x:v[u])if(x!=fa[u]&&x!=son[u])dfs2(x);
    if(son[u])dfs2(son[u]);
    for(int x:v[u])if(x!=fa[u]&&x!=son[u])ins(x);
    Ins(u);++tim;
    if(son[fa[u]]^u){
        T[0].clear();T[1].clear();
        T[0].st.insert(m_p(m_p(1,n),tim));
    }
}
ll res[maxn];
struct Qu {
    int l,r,sgn,id;
};
vector<Qu>Q[maxn];
struct nd {
    ll k,b;
    nd(){k=b=0;}
    nd(ll _k,ll _b){k=_k,b=_b;}
};
nd operator+(nd a,nd b){
    return nd(a.k+b.k,a.b+b.b);
}nd operator*(nd a,int b){
    return nd(a.k*b,a.b*b);
}struct SegTree {
    struct node {
        nd sm,lz;int len;
    }d[maxn<<2];
    #define sm(p) d[p].sm
    #define lz(p) d[p].lz
    #define len(p) d[p].len
    #define ls(p) (p<<1)
    #define rs(p) (p<<1|1)
    void pu(int p){sm(p)=sm(ls(p))+sm(rs(p));}
    void cl(int p,nd x){
        lz(p)=lz(p)+x,sm(p)=sm(p)+x*len(p);
    }void pd(int p){cl(ls(p),lz(p)),cl(rs(p),lz(p)),lz(p)=nd(0,0);}
    void modify(int l,int r,int s,int t,int p,nd k){
        if(l<=s&&t<=r){cl(p,k);return;}pd(p);
        int mid=s+t>>1;
        if(l<=mid)modify(l,r,s,mid,ls(p),k);if(r>=mid+1)modify(l,r,mid+1,t,rs(p),k);pu(p);
    }nd qry(int l,int r,int s,int t,int p){
        if(l<=s&&t<=r)return sm(p);pd(p);
        int mid=s+t>>1;nd res(0,0);
        if(l<=mid)res=res+qry(l,r,s,mid,ls(p));if(r>=mid+1)res=res+qry(l,r,mid+1,t,rs(p));
        return res;
    }
    void bd(int l,int r,int p){
        len(p)=r-l+1;if(l==r)return;
        int mid=l+r>>1;
        bd(l,mid,ls(p)),bd(mid+1,r,rs(p));
    }
}Tree;
void slv(){
    n=read();
    up(i,1,n-1){
        int x=read(),y=read();
        v[x].p_b(y),v[y].p_b(x);
    }dfs(1);T[0].st.insert(m_p(m_p(1,n),tim));dfs2(1);
    int q=read();up(i,1,q){
        int l=read(),r=read();
        Q[r].p_b((Qu){l,r,1,i});
        Q[l-1].p_b((Qu){l,r,-1,i});
    }Tree.bd(1,n,1);
    up(i,1,n){
        for(auto it:vec[i])Tree.modify(it.p1.p1,it.p1.p2,1,n,1,nd(it.p2,-it.p2*1ll*(i-1)));
        for(auto it:Q[i]){
            nd w=Tree.qry(it.l,it.r,1,n,1);
            res[it.id]+=(i*1ll*w.k+w.b)*1ll*it.sgn;
        }
    }up(i,1,q)printf("%lld\n",res[i]/2);
}int main(){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    slv();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

LYLAKIOI  •  1年前

比赛已结束。