本文共 2315 字，大约阅读时间需要 7 分钟。
这题只需在sdoi2011染色的基础上，将边权转到点权。然后询问的时候在一条链上的情况，深度小的dfn+1查询。如果在一条链上还是同一个点，判断上次的两个是否相同，相同-1，然后直接返回。
数据里没有cost=0,的情况，没有询问a=b的情况，甚至lazy都不用清空，甚至update里x一直都不等于y,以至于不可能ql>qr。不过开始arr错了。
典型数据：
1 7 1
Q 3 5
Q 3 7
Q 3 7最后跳到同一个点，判断2边上次查询值一样，减1返回。
#include #include #include #include #include #include #include #include #include #include #include #include #include #define mkp make_pair#define err cout<<"err"< pii;const lon SZ=100010,SSZ=2*SZ,APB=4,one=1;const lon INF=0x3f3f3f3f,mod=2147493647;lon n,m,arr[SZ];struct nd{ int to,wt; nd(int a=0,int b=0):to(a),wt(b){}};vector mp[SZ];int top[SZ],dfn[SZ],cnt;int siz[SZ],hy[SZ],pre[SZ],dep[SZ];int num[5*SZ],lc[5*SZ],rc[5*SZ];int lazy[5*SZ];void dfs1(int x,int p,int d){ siz[x]=1,pre[x]=p,dep[x]=d; for(int i=0;i siz[hy[x]]) { hy[x]=to; } } }}void dfs2(int x,int p,int t){ dfn[x]=++cnt; top[x]=t; if(hy[x])dfs2(hy[x],x,t); for(int i=0;i rr||ql>qr)return; int mid=(ll+rr)/2; if(ll!=rr)pushdown(rt); if(ql<=ll&&rr<=qr) { num[rt]=1; lc[rt]=rc[rt]=delta; lazy[rt]=delta; return; } if(ql<=mid)update(ll,mid,rt*2,ql,qr,delta); if(qr>mid)update(mid+1,rr,rt*2+1,ql,qr,delta); pushup(rt);}int qry(int ll,int rr,int rt,int ql,int qr,int &cl,int &cr){ if(ll>rr||ql>qr)return 0; int mid=(ll+rr)/2; if(ll!=rr)pushdown(rt); if(ql<=ll&&rr<=qr) { cl=lc[rt],cr=rc[rt]; //cout<<"num: "< < mid)res2=qry(mid+1,rr,rt*2+1,ql,qr,c3,c4); //cout<<"ll: "< <<" "< < dep[y])swap(x,y); update(1,n,1,dfn[x]+1,dfn[y],z);}int qry(int x,int y){ int res=0; lon last1=INF,last2=INF; for(;top[x]!=top[y];) { if(dep[top[x]] dep[y])swap(x,y),swap(last1,last2); int c1,c2; res+=qry(1,n,1,dfn[x]+1,dfn[y],c1,c2); //cout<<"res: "< <<" "< <<" "< < >a>>b>>c; mp[a].push_back(nd(b,c)); mp[b].push_back(nd(a,c)); } dfs1(1,-1,1); dfs2(1,-1,1); for(int i=1;i<=n;++i) { update(1,n,1,dfn[i],dfn[i],arr[i]); } //int c1,c2; //for(int i=1;i<=30;++i)cout< < >ch; int a,b,c; if(ch[0]=='C') { cin>>a>>b>>c; update(a,b,c); //int c1,c2; //cout<<"qry: "< < >a>>b; int res=qry(a,b); if(a==b)res=0; cout< < >casenum; //cout< < >n>>m;++tim) { memset(lazy,0x3f,sizeof(lazy)); //cout<<"Case #"< <<": "; init(); work(); release(); } return 0;}
转载于:https://www.cnblogs.com/gaudar/p/10983704.html