解题思路

快被调死的码农题，，，其实就是一个边权下放到点权的线段树+树剖。

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int MAXN = 100005;const int inf = 0x3f3f3f3f;inline int rd(){    int x=0,f=1;char ch=getchar();    while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}    return f?x:-x;}int n,m,head[MAXN],cnt=1,to[MAXN<<1],nxt[MAXN<<1],val[MAXN<<1],num;int w[MAXN],wt[MAXN],id[MAXN],top[MAXN],siz[MAXN],son[MAXN],fa[MAXN],dep[MAXN];int Sum[MAXN<<2],Min[MAXN<<2],Max[MAXN<<2];bool rev[MAXN<<2],lazy[MAXN<<2];inline void add(int bg,int ed,int ww){    to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt,val[cnt]=ww;}void dfs1(int x,int f,int d){    dep[x]=d,fa[x]=f,siz[x]=1;int maxson=-1,u;    for(register int i=head[x];i;i=nxt[i]){        u=to[i];if(u==f) continue;        dfs1(u,x,d+1);siz[x]+=siz[u];w[u]=val[i];        if(siz[u]>maxson) {maxson=siz[u];son[x]=u;}    }}void dfs2(int x,int topf){    top[x]=topf;id[x]=++num;wt[num]=w[x];    if(!son[x]) return;dfs2(son[x],topf);int u;    for(register int i=head[x];i;i=nxt[i]){        u=to[i];if(u==fa[x] || u==son[x]) continue;        dfs2(u,u);    }}inline void pushdown(int x){    rev[x<<1]^=1;rev[x<<1|1]^=1;rev[x]^=1;    Sum[x<<1]=-Sum[x<<1];Sum[x<<1|1]=-Sum[x<<1|1];    swap(Min[x<<1],Max[x<<1]);swap(Min[x<<1|1],Max[x<<1|1]);    Min[x<<1]=-Min[x<<1];Min[x<<1|1]=-Min[x<<1|1];    Max[x<<1]=-Max[x<<1];Max[x<<1|1]=-Max[x<<1|1];}void build(int x,int l,int r){    if(l==r) {
    if(l==1) Min[x]=inf,Max[x]=-inf; else Sum[x]=Min[x]=Max[x]=wt[l];return;}    int mid=(l+r)>>1;    build(x<<1,l,mid);build(x<<1|1,mid+1,r);    Sum[x]=Sum[x<<1]+Sum[x<<1|1];    Min[x]=min(Min[x<<1],Min[x<<1|1]);    Max[x]=max(Max[x<<1],Max[x<<1|1]);}void update(int x,int l,int r,int L,int R,int ww){    if(L<=l && r<=R) {        if(ww==-inf) {rev[x]^=1;Sum[x]=-Sum[x];swap(Min[x],Max[x]);Min[x]=-Min[x];Max[x]=-Max[x];}        else Sum[x]=Min[x]=Max[x]=ww;        return;    }    int mid=(l+r)>>1;if(rev[x]) pushdown(x);    if(L<=mid) update(x<<1,l,mid,L,R,ww);    if(mid
           
            >1,ret=0;if(rev[x]) pushdown(x); if(L<=mid) ret+=query_Sum(x<<1,l,mid,L,R); if(mid
            
             >1,ret=-inf;if(rev[x]) pushdown(x); if(L<=mid) ret=max(ret,query_Max(x<<1,l,mid,L,R)); if(mid
             
              >1,ret=inf;if(rev[x]) pushdown(x); if(L<=mid) ret=min(ret,query_Min(x<<1,l,mid,L,R)); if(mid
              
               dep[y]) swap(x,y); if(x!=y) update(1,1,n,id[x]+1,id[y],-inf);}inline int qSum(int x,int y){ int ret=0; while(top[x]!=top[y]){ if(dep[top[x]]
               
                dep[y]) swap(x,y); if(x!=y) ret+=query_Sum(1,1,n,id[x]+1,id[y]); return ret;}inline int qMax(int x,int y){ int ret=-inf; while(top[x]!=top[y]){ if(dep[top[x]]
                
                 dep[y]) swap(x,y); if(x!=y) ret=max(ret,query_Max(1,1,n,id[x]+1,id[y])); return ret;}inline int qMin(int x,int y){ int ret=inf; while(top[x]!=top[y]){ if(dep[top[x]]
                 
                  dep[y]) swap(x,y);if(x!=y) ret=min(ret,query_Min(1,1,n,id[x]+1,id[y])); return ret;}inline int pre(int x){ return dep[to[x<<1]]>dep[to[x<<1^1]]?to[x<<1]:to[x<<1^1];}int main(){// freopen("wrong.out","w",stdout); n=rd();int x,y,z;char s[5]; for(int i=1;i