Description
Input
Output
Sample Input
4 3 5
1 9 2
7 6 5 1
2 3
3 1
3 4
1 2 3 2
1 1 2
1 4 2
0 2 1
Sample Output
84
131
27
HINT
Solution
一個講解
還是改成括号序的寫法吧……感覺好了解還好碼……
一開始插入和删除函數是像下面這樣分開寫的,$vis$函數加加減減不知道哪裡錯了……如果有大爺看出來哪裡錯了和我說一聲啊QAQ
1 void Ins(int x)
2 {
3 vis[x]++;
4 if (vis[x]==2) Delicacy-=v[c[x]]*w[Keg[c[x]]], Keg[c[x]]--;
5 else Keg[c[x]]++, Delicacy+=v[c[x]]*w[Keg[c[x]]];
6 }
7
8 void Del(int x)
9 {
10 vis[x]--;
11 if (vis[x]==1) Keg[c[x]]++, Delicacy+=v[c[x]]*w[Keg[c[x]]];
12 else Delicacy-=v[c[x]]*w[Keg[c[x]]], Keg[c[x]]--;
13 }
14
15 void Recov(int x,int val)
16 {
17 if (vis[x]==1) Del(x), c[x]=val, Ins(x);
18 c[x]=val;
19 }
後來改成天下第一的寫法對$vis$搞異或就過了……至今不知道為什麼……
Code
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 #include<algorithm>
5 #define N (200009)
6 #define LL long long
7 using namespace std;
8
9 struct Que{int l,r,t,num,flag; LL ans;}Q[N];
10 struct Mdf{int pre,nxt,pos;}M[N];
11 struct Edge{int to,next;}edge[N<<1];
12 LL Delicacy,v[N],w[N];
13 int n,m,q,x,y,opt,l=1,r,flag,Q_num,M_num,Time,dfs_num;
14 int Keg[N*5],vis[N],ID[N],a[N];
15 int Fir[N],Sec[N],f[N][18],Depth[N],c[N];
16 int head[N],num_edge;
17 bool cmp1(Que a,Que b)
18 {
19 if (ID[a.l]==ID[b.l])
20 return ID[a.r]==ID[b.r]?a.t<b.t:ID[a.r]<ID[b.r];
21 else return ID[a.l]<ID[b.l];
22 }
23 bool cmp2(Que a,Que b) {return a.num<b.num;}
24
25 void add(int u,int v)
26 {
27 edge[++num_edge].to=v;
28 edge[num_edge].next=head[u];
29 head[u]=num_edge;
30 }
31
32 void Ins(int x)
33 {
34 if (vis[x]) Delicacy-=v[c[x]]*w[Keg[c[x]]], Keg[c[x]]--;
35 else Keg[c[x]]++, Delicacy+=v[c[x]]*w[Keg[c[x]]];
36 vis[x]^=1;
37 }
38
39 void Recov(int x,int val)
40 {
41 if (vis[x]) Ins(x),c[x]=val,Ins(x);
42 else c[x]=val;
43 }
44
45 void MoQueue(int num)
46 {
47 while (Time<Q[num].t) Recov(M[Time+1].pos,M[Time+1].nxt), Time++;
48 while (Time>Q[num].t) Recov(M[Time].pos,M[Time].pre), Time--;
49 while (l<Q[num].l) Ins(a[l++]);
50 while (l>Q[num].l) Ins(a[--l]);
51 while (r<Q[num].r) Ins(a[++r]);
52 while (r>Q[num].r) Ins(a[r--]);
53 Q[num].ans=Delicacy;
54 if (Q[num].flag)
55 {
56 Ins(Q[num].flag);
57 Q[num].ans=Delicacy;
58 Ins(Q[num].flag);
59 }
60 }
61
62 void DFS(int x,int fa)
63 {
64 f[x][0]=fa;
65 for (int i=1; i<=17; ++i) f[x][i]=f[f[x][i-1]][i-1];
66 Depth[x]=Depth[fa]+1; Fir[x]=++dfs_num;
67 a[dfs_num]=x;
68 for (int i=head[x]; i; i=edge[i].next)
69 if (edge[i].to!=fa) DFS(edge[i].to,x);
70 Sec[x]=++dfs_num; a[dfs_num]=x;
71 }
72
73 int LCA(int x,int y)
74 {
75 if (Depth[x]<Depth[y]) swap(x,y);
76 for (int i=17; i>=0; --i)
77 if (Depth[f[x][i]]>=Depth[y]) x=f[x][i];
78 if (x==y) return x;
79 for (int i=17; i>=0; --i)
80 if (f[x][i]!=f[y][i]) x=f[x][i], y=f[y][i];
81 return f[x][0];
82 }
83 int main()
84 {
85 scanf("%d%d%d",&n,&m,&q);
86 int unit=pow(n,2.0/3.0);
87 for (int i=1; i<=(n*2); ++i) ID[i]=(i-1)/unit+1;
88 for (int i=1; i<=m; ++i) scanf("%lld",&v[i]);
89 for (int i=1; i<=n; ++i) scanf("%lld",&w[i]);
90 for (int i=1; i<=n-1; ++i)
91 scanf("%d%d",&x,&y), add(x,y), add(y,x);
92 for (int i=1; i<=n; ++i) scanf("%d",&c[i]);
93 DFS(1,0);
94 for (int i=1; i<=q; ++i)
95 {
96 scanf("%d%d%d",&opt,&x,&y);
97 if (opt==1)
98 {
99 if (Fir[x]>Fir[y]) swap(x,y);
100 int lca=LCA(x,y);
101 if (lca==x) x=Fir[x], y=Fir[y], flag=0;
102 else x=Sec[x], y=Fir[y], flag=lca;
103 Q[++Q_num]=(Que){x,y,M_num,i,flag,0};
104 }
105 else M[++M_num]=(Mdf){c[x],y,x}, c[x]=y;
106 }
107 for (int i=M_num; i>=1; --i)
108 c[M[i].pos]=M[i].pre;
109 sort(Q+1,Q+Q_num+1,cmp1);
110 for (int i=1; i<=Q_num; ++i)
111 MoQueue(i);
112 sort(Q+1,Q+Q_num+1,cmp2);
113 for (int i=1; i<=Q_num; ++i)
114 printf("%lld\n",Q[i].ans);
115 }