早有耳闻的sxbk题

一直以为带修改树上莫队一定有着很高的技巧

于是去膜了一发题解

才发现这道题主要是在排序上面加特技

考虑将询问分块，然后与普通莫队不同的地方是我们将询问按照左端点的块编号、右端点的块编号、在第几次修改之后三个关键字排序。

这样在n^(2/3)个块区间里面的修改因为时间有序了所以是O(n)的。然后询问的话反正区间内的修改是n^(2/3)的，区间开头的询问也可以暴力O(n)搞。

所以时间的操作是O(n^(5/3))的，而其他树上莫队的部分也是O(n^(5/3))

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100050
#define M 400050
#define ll long long
#define eps 1e-5
int c[N*2][2],fi[N],fa[N],sg[N][2],rt,n,m,Sign[M],t[M];
int li[N],cl[N],mo[N][3],qu[N][2],ss,st,p,cnt[N];
int now,nt[M];ll ans[N],Ans,tot[N];
struct Color
 {
 	ll wi[N],v[N],s[N];
 	inline void Insert(int x)
 	 {Ans+=wi[++s[x]]*v[x];}
 	inline void Delete(int x)
 	 {Ans-=wi[s[x]--]*v[x];}
 } Aha;
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar(); while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return x;
 }
inline void Line(int x,int y)
 {
 	c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
 	c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
 }
void DFS(int x)
 {
 	nt[sg[x][0]=++st]=x;tot[x]=2;
 	for (int i=fi[x];i;i=c[i][1])
 	 if (c[i][0]!=fa[x])
 	  {
 	  	 if (nt[st]!=x) nt[++st]=x,tot[x]++;
 	   	 fa[c[i][0]]=x,DFS(c[i][0]);
 	  }
 	nt[sg[x][1]=++st]=x;
 }
inline bool cmp(int x,int y)
 {return Sign[qu[x][0]]<Sign[qu[y][0]]||
   (Sign[qu[x][0]]==Sign[qu[y][0]]&&(Sign[qu[x][1]]<
   	  Sign[qu[y][1]]||(Sign[qu[x][1]]==Sign[qu[y][1]]&&
   	    t[x]<t[y])));}
void Pretreat()
 {
 	DFS(1);
 	rt=pow(st,2.0/3.0)+eps;
 	for (int i=1;i<=st;i++) Sign[i]=(i-1)/rt;
 	for (int i=1;i<=p;i++)
 	 {
 	 	if (sg[qu[i][1]][0]<sg[qu[i][0]][0])
 	 	  swap(qu[i][1],qu[i][0]);
 	 	qu[i][0]=sg[qu[i][0]][sg[qu[i][0]][1]<sg[qu[i][1]][1]];
 	 	qu[li[i]=i][1]=sg[qu[i][1]][0];
 	 }
 	for (int i=1;i<=now;i++)
 	  mo[i][1]=cl[mo[i][0]],cl[mo[i][0]]=mo[i][2];
 	for (int i=now;i>=1;i--)
 	  cl[mo[i][0]]=mo[i][1];
 	sort(li+1,li+p+1,cmp);
 }
inline void Move(int x,int y)
 {
 	bool r=(cnt[mo[x][0]]<tot[mo[x][0]])
 	   &&(cnt[mo[x][0]]>0);
 	if (r) Aha.Delete(mo[x][y]);
 	cl[mo[x][0]]=mo[x][3-y];
 	if (r) Aha.Insert(mo[x][3-y]);
 }
inline void Modify(int x,int y)
 {
 	cnt[x]+=y;
 	if (!cnt[x]||cnt[x]==tot[x]) Aha.Delete(cl[x]); else
 	 if (cnt[x]-y==0||cnt[x]-y==tot[x]) Aha.Insert(cl[x]);
 }
void Solve()
 {
 	int le=1,ri=0;now=0;
 	for (int i=1;i<=p;i++)
 	 {
 	 	int k=qu[li[i]][0],l=qu[li[i]][1];
 	 	for (;le<k;le++) Modify(nt[le],-1);
 	 	for (;le>k;) Modify(nt[--le],1);
 	 	for (;ri>l;ri--) Modify(nt[ri],-1);
 	 	for (;ri<l;) Modify(nt[++ri],1);
 	 	for (;now<t[li[i]];) Move(++now,1);
 	 	for (;now>t[li[i]];) Move(now--,2);
 	 	ans[li[i]]=Ans;
 	 }
 	return;
 }
int main()
 {
 	n=Read();m=Read();p=Read();
 	for (int i=1;i<=m;i++) Aha.v[i]=Read();
 	for (int i=1;i<=n;i++) Aha.wi[i]=Read();
 	for (int i=1;i<n;i++)
 	  Line(Read(),Read());
 	for (int i=1;i<=n;i++) cl[i]=Read();
 	int o=p;p=0;
    while (o--)
 	 if (Read())
 	   qu[++p][0]=Read(),qu[p][1]=Read(),t[p]=now;else
 	   mo[++now][0]=Read(),mo[now][2]=Read();
 	Pretreat();
 	Solve();
 	for (int i=1;i<=p;i++)
 	  printf("%lld\n",ans[i]);
 	return 0;
 }