BZOJ 3052: [wc2013]糖果公园

Description

Candyland 有一座糖果公园，公园里不仅有美丽的风景、好玩的游乐项目，还有许多免费糖果的发放点，这引来了许多贪吃的小朋友来糖果公园玩。

糖果公园的结构十分奇特，它由 n 个游览点构成，每个游览点都有一个糖果发放处，我们可以依次将游览点编号为 1 至 n。有 n−1 条双向道路连接着这些游览点，并且整个糖果公园都是连通的，即从任何一个游览点出发都可以通过这些道路到达公园里的所有其它游览点。

糖果公园所发放的糖果种类非常丰富，总共 m 种，它们的编号依次为 1 至 m。每一个糖果发放处都只发放某种特定的糖果，我们用 ci 来表示 i 号游览点的糖果。

来到公园里游玩的游客都不喜欢走回头路，他们总是从某个特定的游览点出发前往另一个特定的游览点，并游览途中的景点，这条路线一定是唯一的。他们经过每个游览点，都可以品尝到一颗对应种类的糖果。

大家对不同类型的糖果的喜爱程度都不尽相同。根据游客们的反馈打分，我们得到了糖果的美味指数，第 i 种糖果的美味指数为 vi。另外，如果一位游客反复地品尝同一种类的糖果，他肯定会觉得有一些腻。根据量化统计，我们得到了游客第 i 次品尝某类糖果的新奇指数 wi，如果一位游客第 i 次品尝第 jj 种糖果，那么他的愉悦指数 H 将会增加对应的美味指数与新奇指数的乘积，即 vjwi。这位游客游览公园的愉悦指数最终将是这些乘积的和。

当然，公园中每个糖果发放点所发放的糖果种类不一定是一成不变的。有时，一些糖果点所发放的糖果种类可能会更改（也只会是 m 种中的一种），这样的目的是能够让游客们总是感受到惊喜。

糖果公园的工作人员小 A 接到了一个任务，那就是根据公园最近的数据统计出每位游客游玩公园的愉悦指数。但数学不好的小 A 一看到密密麻麻的数字就觉得头晕，作为小 A 最好的朋友，你决定帮他一把。

Input

第一行包含三个正整数 n,m,qn,m,q，分别表示游览点个数、糖果种类数和操作次数。

第二行包含 mm 个正整数 v1,v2,…,vmv1,v2,…,vm。

第三行包含 nn 个正整数 w1,w2,…,wnw1,w2,…,wn。

第四行到第 n+2n+2 行，每行包含两个正整数 ai,biai,bi，表示这两个游览点之间有路径可以直接到达。

第 n+3n+3 行包含 nn 个正整数 c1,c2,…,cnc1,c2,…,cn。

接下来 qq 行，每行包含三个整数 t,x,yt,x,y，表示一次操作：

若 tt 为 00，则 1≤x≤n1≤x≤n，1≤y≤m1≤y≤m，表示编号为 xx 的游览点发放的糖果类型改为 yy；

若 tt 为 11，则 1≤x,y≤n1≤x,y≤n，表示对出发点为 xx，终止点为 yy 的路线询问愉悦指数。

Output

按照输入的先后顺序，对于每个 tt 为 11 的操作输出一行，用一个正整数表示答案。

Sample Input

Sample Output

Constraint

对于所有的数据，1≤vi,wi≤1061≤vi,wi≤106，1≤ai,bi≤n1≤ai,bi≤n，1≤ci≤m1≤ci≤m，w1,w2,…,wnw1,w2,…,wn 是非递增序列，即对任意 1<i≤n1<i≤n，满足 wi≤wi−1wi≤wi−1。测试点编号nmq其它限制1≤20≤20≤20≤20≤20≤20无2≤2000≤2000≤2000≤2000≤2000≤20003≤10000≤10000≤10000≤10000≤10000≤100004≤80000≤80000≤100≤100≤80000≤80000没有修改操作；给出的图构成一条链5≤90000≤90000≤100≤100≤90000≤900006≤80000≤80000≤80000≤80000≤80000≤80000没有修改操作7≤90000≤90000≤90000≤90000≤90000≤900008≤80000≤80000≤80000≤80000≤80000≤80000给出的图构成一条链9≤90000≤90000≤90000≤90000≤90000≤9000010≤100000≤100000≤100000≤100000≤100000≤100000无

Solution

树上分块+莫队。

一看题目要求颜色的balabala，直接维护肯定很难，就用莫队好啦！

先给树分快，然后对于每个操作记录一个时间戳。

将操作排序，莫队+树上移动端点即可。（貌似不用求LCA？复杂度是不是有点高。。）

这道题看到uoj上的最短代码还不够短，又给改了改。。

Code

鬼畜版

1
2
3
4
5
6
7
8
#include<bits/stdc++.h>
#define N 100100]
#define J for
#define A x]
#define E i]
#define z(x) for(i=1;i<=x;++i)
typedef int _;
using namespace std;_ n,m,k,i,x,y,t,L,R,l1,l2,tp,d,T,H,S=999,I[N,c[N,v[N,w[N,h[N,s[N,l[N,r[N,D[N,W[2*N,o[2*N,B[N,e[2*N,u[2*N,F[N[18];struct Q{_ l,r,T,d;}q[N;struct P{_ x,p,o;}p[N;bool V[N;long long U,X[N;bool Y(Q a,Q b){return W[a.l]<W[b.l]||W[a.l]==W[b.l]&&W[a.r]<W[b.r]||W[a.l]==W[b.l]&&W[a.r]==W[b.r]&&a.T<b.T;}void ins(_ x,_ y){u[++H]=y;e[H]=B[A;B[A=H;}void Z(_ x){_ i;D[A=++tp;l[A=++d;o[d]=x;J(i=1;i<=17;i++)F[A[E=F[F[A[i-1]][i-1];J(i=B[A;i;i=e[E)if(F[A[0]!=u[E)F[u[E][0]=x,h[u[E]=h[A+1,Z(u[E);r[A=++d;o[d]=x;}_ C(_ x,_ y){if(h[A<h[y])swap(x,y);_ t=h[A-h[y],i;J(i=0;i<=17;i++)if(t>>i&1)x=F[A[E;J(i=17;i>=0;i--)if(F[A[E!=F[y][E)x=F[A[E,y=F[y][E;return x==y?x:F[A[0];}void g(_ x){if(V[A)U-=1ll*v[c[A]*w[s[c[A]--];else U+=1ll*v[c[A]*w[++s[c[A]];V[A^=1;}void O(_ x,_ y){if(V[A)g(x),c[A=y,g(x);else c[A=y;}_ main(){J(scanf("%d%d%d",&n,&m,&k),i=1;i<=m;i++)scanf("%d",&v[E);z(n)scanf("%d",&w[E);z(n-1)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);z(n)scanf("%d",&c[E),I[E=c[E;J(Z(1),i=1;i<=d;i++)W[E=(i-1)/S;J(i=1;i<=k;i++)if(scanf("%d%d%d",&t,&x,&y),t){if(D[A>D[y])swap(x,y);q[++l1].r=l[y];q[l1].d=l1;q[l1].T=l2;t=C(x,y);if(t==x)q[l1].l=l[A;else q[l1].l=r[A;}else p[++l2].x=x,p[l2].p=I[A,p[l2].o=I[A=y;J(sort(q+1,q+l1+1,Y),L=1,R=0,T=i=1;i<=l1;i++){J(;T<=q[E.T;T++)O(p[T].x,p[T].o);J(;T>q[E.T;T--)O(p[T].x,p[T].p);J(;L>q[E.l;g(o[--L]));J(;L<q[E.l;g(o[L++]));J(;R>q[E.r;g(o[R--]));J(;R<q[E.r;g(o[++R]));x=o[L];y=o[R];t=C(x,y);if(x!=t&&y!=t)g(t);X[q[E.d]=U;if(x!=t&&y!=t)g(t);}z(l1)printf("%lld\n",X[E);}

正常版

  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
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 100005;
const int siz = 2154;
inline int getint() {
    int r = 0; bool b = true; char c = getchar();
    while ('0' > c || c > '9') { if (c == '-') b = false; c = getchar(); }
    while ('0' <= c && c <= '9') { r = r * 10 + (c - '0'); c = getchar(); }
    if (b) return r;
    return -r;
}
LL ANS[maxn], v[maxn], w[maxn], ans;
int n, fa[maxn], X[maxn], tot, dep[maxn], c[maxn], tail, sta[maxn], h[maxn], to[maxn<<1], nex[maxn<<1], cnte, a[maxn], b[maxn], bec[maxn], bef[maxn], cnt[maxn];
bool wtf[maxn], vis[maxn];
struct query_t {
    int t, x, y, id;
    void init(int _) {
        id = _;
        t = getint();
        x = getint();
        y = getint();
        if (t) { if (c[x] > c[y]) swap(x, y); wtf[_] = true; }
        else { bec[_] = y; bef[_] = a[x]; X[_] = x; a[x] = y; }
    }
} que[maxn];
bool cmp(query_t a, query_t b) {
    if (a.t != b.t) return a.t < b.t;
    if (a.t == 0) return a.id < b.id;
    if (c[a.x] != c[b.x]) return c[a.x] < c[b.x];
    if (c[a.y] != c[b.y]) return c[a.y] < c[b.y];
    return a.id < b.id;
}
void ins(int x, int y) { to[++cnte] = y; nex[cnte] = h[x]; h[x] = cnte; }
void dfs(int now, int father, int deep) {
    dep[now] = deep; fa[now] = father;
    int st = tail;
    for (int i = h[now]; i; i = nex[i]) {
        if (to[i] == father) continue;
        dfs(to[i], now, deep + 1);
        if (tail - st >= siz) {
            ++tot;
            while (tail > st) c[sta[tail--]] = tot;
        }
    }
    sta[++tail] = now;
        if (tail - st >= siz) {
            ++tot;
            while (tail > st) c[sta[tail--]] = tot;
        }
}
void INS(int x) { ans += v[x] * w[++cnt[x]]; }
void DEL(int x) { ans -= v[x] * w[cnt[x]--]; }
void FOR(int x) {
    if (wtf[x]) return;
    if (vis[X[x]]) {
        DEL(b[X[x]]);
        INS(bec[x]);
    }
    b[X[x]] = bec[x];
}
void BAC(int x) {
    if (wtf[x]) return;
    if (vis[X[x]]) {
        DEL(b[X[x]]);
        INS(bef[x]);
    }
    b[X[x]] = bef[x];
}
int dst1[maxn], tot1, dst2[maxn], tot2;
void Move(int &s, int t) {
    tot1 = 0;
    int nx = s, ny = t; 
    s = t;
    while (dep[nx] > dep[ny]) { dst1[++tot1] = nx; nx = fa[nx]; }
    while (dep[nx] < dep[ny]) { dst2[++tot2] = ny; ny = fa[ny]; }
    while (nx != ny) {
        dst1[++tot1] = nx; nx = fa[nx];
        dst2[++tot2] = ny; ny = fa[ny];
    }
    dst1[++tot1] = nx;
    while (tot2) dst1[++tot1] = dst2[tot2--];
    for (int i = tot1; i >= 1; --i) if (vis[dst1[i]]) {
        for (int j = 1; j < i; ++j) {
            vis[dst1[j]] = false;
            DEL(b[dst1[j]]);
        }
        for (int j = i + 1; j <= tot1; ++j) {
            vis[dst1[j]] = true;
            INS(b[dst1[j]]);
        }
        return ;
    }
}
int main() {
    int x, y, m, q;
    n = getint(); m = getint(); q = getint();
    for (int i = 1; i <= m; ++i) v[i] = getint();
    for (int i = 1; i <= n; ++i) w[i] = getint();
    for (int i = 1; i < n; ++i) {
        x = getint(); y = getint();
        ins(x, y); ins(y, x);
    }
    dfs(1, 0, 1);
    if (tail > 0) { ++tot; for (int i = 1; i <= n; ++i) ++c[i]; }
    for (int i = 1; i <= n; ++i) a[i] = b[i] = getint();
    for (int i = 1; i <= q; ++i) que[i].init(i);
    sort(que + 1, que + q + 1, cmp);
    int A = 1, B = 1, C, T = 0;
    vis[1] = true; ans = w[1] * v[b[1]]; cnt[b[1]] = 1;
    for (int i = 1; i <= q; ++i) {
        if (que[i].t == 0) ANS[que[i].id] = -1;
        else {
            Move(A, que[i].x);
            Move(B, que[i].y);
            while (T < que[i].id) FOR(++T);
            while (T > que[i].id) BAC(T--);
            ANS[T] = ans;
        }
    }
    for (int i = 1; i <= q; ++i)
        if (ANS[i] != -1) printf("%lld\n", ANS[i]);
}