传送门 https://www.luogu.org/problemnew/show/P4074
总算会树形莫队了......
上次听说树形莫队是给树分块, 实在看不懂. 然后用括号序列的方法做总算能弄明白了
先说一下什么是括号序列, 就是在 $dfs$ 的时候, 进入的时候记录一下, 出去的时候也记录一下
拿样例为例, 它的括号序列就是 $12443321$
那么我们扩展区间对答案的贡献是可以 $O(1)$ 计算的
假设扩展出的点的颜色是 $c$, 那么变化量为 $val_c*worth_{cnt_c+1}$
因为括号序列它在扩展的时候会把子树里的扫两遍, 那么就可以把子树中的答案去掉了
怎么去掉呢? 记录一个 $vis$ 然后每次扫到的时候异或一下, 看看是否被扫过就行了
然而有几个问题
第一,$LCA$ 不是路径端点的话不会被记入答案
考虑上面的括号序列, 如果要从 $4$ 到 $3$ 那么 $2$ 是不会被计入答案的
第二, 起点不是 $LCA$ 的话不会被记入答案
考虑上面,$u$ 被算了两次, 刚好把自己给减掉了
所以上面的两种情况要特判
然后因为是带修莫队, 所以再加上时间这一维
还有这题细节挺多的...... 我因为跳时间轴的时候一个地方写错 WA 了好久......
- //minamoto
- #include
- #include
- #include
- #include
- #include
- #define ll long long
- using namespace std;
- #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
- char buf[1<<21],*p1=buf,*p2=buf;
- inline int read(){
- #define num ch-'0'
- char ch;bool flag=0;int res;
- while(!isdigit(ch=getc()))
- (ch=='-')&&(flag=true);
- for(res=num;isdigit(ch=getc());res=res*10+num);
- (flag)&&(res=-res);
- #undef num
- return res;
- }
- char sr[1<<21],z[30];int C=-1,Z;
- inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
- inline void print(ll x){
- if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
- while(z[++Z]=x%10+48,x/=10);
- while(sr[++C]=z[Z],--Z);sr[++C]='\n';
- }
- const int N=100005;
- struct query{
- int x,y,l,r,id,t;
- }q[N];int q1;
- struct change{int x,c;}t[N];int q2;
- int n,m,L,R,T,s,Q;ll now,ans[N];
- int ver[N<<1],edge[N<<1],head[N],Next[N<<1],top[N],dfn[N],dep[N],sz[N],son[N],lis[N<<1],fa[N],tot,num;
- int vis[N],col[N],wor[N],cnt[N],val[N];
- inline bool cmp(const query a,const query b){
- if(a.l^b.l) return a.l<b.l;
- if(a.r^b.r) return a.l&1?a.r<b.r:a.r>b.r;
- return (a.l^a.r)&1?a.t<b.t:a.t>b.t;
- }
- inline void add(int u,int v){
- ver[++tot]=v,Next[tot]=head[u],head[u]=tot;
- ver[++tot]=u,Next[tot]=head[v],head[v]=tot;
- }
- void dfs(int u){
- dep[u]=dep[fa[u]]+1,sz[u]=1;
- for(int i=head[u];i;i=Next[i]){
- int v=ver[i];
- if(v!=fa[u]){
- fa[v]=u,dfs(v),sz[u]+=sz[v];
- if(sz[v]>sz[son[u]]) son[u]=v;
- }
- }
- }
- void dfs(int u,int t){
- top[u]=t,lis[dfn[u]=++num]=u;
- if(son[u]) dfs(son[u],t);
- for(int i=head[u];i;i=Next[i]){
- if(ver[i]!=fa[u]&&ver[i]!=son[u]) dfs(ver[i],ver[i]);
- }
- lis[++num]=u;
- }
- inline int LCA(int u,int v){
- while(top[u]!=top[v]){
- if(dep[top[u]]<dep[top[v]]) swap(u,v);
- u=fa[top[u]];
- }
- return dep[u]<dep[v]?u:v;
- }
- inline void sol(int x){
- int c=col[x];
- (vis[x]^=1)?now+=(ll)wor[++cnt[c]]*val[c]:now-=(ll)wor[cnt[c]--]*val[c];
- }
- inline void mdy(int i){
- int u=t[i].x,x=t[i].c,y=col[u];
- if(vis[u]) now+=(ll)wor[++cnt[x]]*val[x]-(ll)wor[cnt[y]--]*val[y];
- t[i].c=y,col[u]=x;
- }
- int main(){
- n=read(),m=read(),Q=read();
- for(int i=1;i<=m;++i) val[i]=read();
- for(int i=1;i<=n;++i) wor[i]=read();
- for(int i=1;i<n;++i){
- int u=read(),v=read();add(u,v);
- }
- for(int i=1;i<=n;++i) col[i]=read();
- dfs(1),dfs(1,1);
- while(Q--){
- int opt=read(),x=read(),y=read();
- if(opt){if(dfn[x]>dfn[y]) swap(x,y);
- q[++q1]=(query){x,y,dfn[x],dfn[y],q1,q2};
- }
- else t[++q2]=(change){x,y};
- }
- s=pow(n,q2?2.0/3:1.0/2);
- for(int i=1;i<=n;++i) q[i].l/=s,q[i].r/=s;
- sort(q+1,q+1+q1,cmp),L=dfn[q[1].l],R=L-1,T=0;
- for(int i=1;i<=q1;++i){
- int u=q[i].x,v=q[i].y;
- int l=dfn[u],r=dfn[v],g=q[i].t;
- while(L>l) sol(lis[--L]);
- while(R<r) sol(lis[++R]);
- while(L<l) sol(lis[L++]);
- while(R>r) sol(lis[R--]);
- while(T<g) mdy(++T);
- while(T>g) mdy(T--);
- //LCA 不是路径端点的话是不会计算的
- // 出发点 u 如果不是 LCA 也是不会计算的
- // 这两个都要特判
- int p=LCA(u,v);
- if(u!=p){sol(u);if(v!=p) sol(p);}
- ans[q[i].id]=now;
- if(u!=p){sol(u);if(v!=p) sol(p);}
- }
- for(int i=1;i<=q1;++i) print(ans[i]);
- Ot();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2743379.html