「WC2013」糖果公园

发表于 | 分类于 | | 浏览量： 次

吃个糖果还这么多事情。

传送门

洛谷P4074

BZOJ3052

题解

树上带修莫队的板子题，以前一直没写。

树上莫队的话就需要先对树进行分块，王室联邦分块即可。

移动端点的时候可以先把路径存下来，然后再按顺序移动。

块大小取$n^{\frac{2}{3}}$时比较优。

其他照常写就好了，注意常数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100005;
int n,m,q,c,tot,lnk[maxn],son[maxn*2],nxt[maxn*2],dep[maxn],fa[maxn],W[maxn],V[maxn],C[maxn],S,cnt,Area[maxn],top,stk[maxn],hsh[maxn],pa[maxn];LL ans[maxn],now;bool vis[maxn];
struct FastIO
{
	static const int S=1048576;
	char buf[S],*L,*R;int stk[20],Top;
	~FastIO(){clear();}
	inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}
	inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
	inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}
	FastIO& operator >> (int& ret)
	{
		ret=0;int f=1;char ch=nc();
		while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
		while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}
		ret*=f;return *this;
	}
	FastIO& operator << (LL x)
	{
		if(x<0){pc('-');x=-x;}
		do{stk[++stk[0]]=x%10;x/=10;}while(x);
		while(stk[0]) pc('0'+stk[stk[0]--]);
		return *this;
	}
	FastIO& operator << (char ch){pc(ch);return *this;}
}fin,fout;
struct Query
{
	int L,R,t,id;
	bool operator < (const Query& b)const{return Area[L]<Area[b.L]||(Area[L]==Area[b.L]&&Area[R]<Area[b.R])||(Area[L]==Area[b.L]&&Area[R]==Area[b.R]&&t<b.t);}
}Q[maxn];
struct Change{int t,x,y,lst;}CK[maxn];
inline void add_e(int x,int y){tot++;son[tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
void DFS(int now)
{
	int lst=top;stk[++top]=now;dep[now]=dep[fa[now]]+1;
	for(int i=lnk[now];i;i=nxt[i])
	{
		if(son[i]==fa[now]) continue;
		fa[son[i]]=now;DFS(son[i]);
		if(top-lst>=S)
		{
			cnt++;
			while(top!=lst){Area[stk[top]]=cnt;top--;}
		}
	}
}
inline void Inc(int x){hsh[x]++;now+=(LL)V[x]*W[hsh[x]];}
inline void Dec(int x){now-=(LL)V[x]*W[hsh[x]];hsh[x]--;}
inline void Init()
{
	static int tep[maxn];
	DFS(1);q-=c;sort(Q+1,Q+1+q);
	if(top){cnt++;while(top){Area[stk[top]]=cnt;top--;}}
	memcpy(tep,C,sizeof(C));
	for(int i=1;i<=c;i++)
	{
		CK[i].lst=tep[CK[i].x];
		tep[CK[i].x]=CK[i].y;
	}
}
inline void GetDist(int u,int v)
{
	static int stk[maxn],top;
	pa[0]=top=0;pa[++pa[0]]=u;stk[++top]=v;
	while(u!=v)
	{
		if(dep[u]>=dep[v]){u=fa[u];pa[++pa[0]]=u;}
		else{v=fa[v];stk[++top]=v;}
	}
	for(int i=top-1;i;i--) pa[++pa[0]]=stk[i];
}
inline void Solve()
{
	int L=1,R=1,t=0;vis[1]=true;Inc(C[1]);
	for(int i=1;i<=q;i++)
	{
		if(L!=Q[i].L)
		{
			GetDist(L,Q[i].L);
			for(int j=1;j<pa[0];j++)
			{
				if(vis[pa[j+1]]){Dec(C[pa[j]]);vis[pa[j]]=false;}
				else{Inc(C[pa[j+1]]);vis[pa[j+1]]=true;}
			}
			L=Q[i].L;
		}
		if(R!=Q[i].R)
		{
			GetDist(R,Q[i].R);
			for(int j=1;j<pa[0];j++)
			{
				if(vis[pa[j+1]]){Dec(C[pa[j]]);vis[pa[j]]=false;}
				else{Inc(C[pa[j+1]]);vis[pa[j+1]]=true;}
			}
			R=Q[i].R;
		}
		while(t<c&&CK[t+1].t<Q[i].t)
		{
			t++;
			if(vis[CK[t].x]) Dec(CK[t].lst);
			C[CK[t].x]=CK[t].y;
			if(vis[CK[t].x]) Inc(CK[t].y);
		}
		while(CK[t].t>Q[i].t)
		{
			if(vis[CK[t].x]) Dec(CK[t].y);
			C[CK[t].x]=CK[t].lst;
			if(vis[CK[t].x]) Inc(CK[t].lst);
			t--;
		}
		ans[Q[i].id]=now;
	}
}
int main()
{
	fin>>n>>m>>q;S=pow(n,2.0/3)+1e-10;
	for(int i=1;i<=m;i++) fin>>V[i];
	for(int i=1;i<=n;i++) fin>>W[i];
	for(int i=1;i<n;i++)
	{
		int a,b;fin>>a>>b;
		add_e(a,b);add_e(b,a);
	}
	for(int i=1;i<=n;i++) fin>>C[i];
	for(int i=1;i<=q;i++)
	{
		int opt;fin>>opt;
		if(opt){fin>>Q[i-c].L>>Q[i-c].R;Q[i-c].id=i-c;Q[i-c].t=i;}
		else{c++;fin>>CK[c].x>>CK[c].y;CK[c].t=i;}
	}
	Init();Solve();
	for(int i=1;i<=q;i++)
		fout<<ans[i]<<'\n';
	return 0;
}