BZOJ 3052: [wc2013]糖果公园

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
HINT
题解
代码

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

1 1 2

1 4 2

Sample Output

131

HINT

题解

在写了苹果树的基础上再来写糖果公园就简单多了！这是暴力的O(n)的价值转移+O(t)的时间转移。
我们这么想对于每个修改，我么只需要把时间恢复到走那条路径时候的时间就可以了，然后和苹果树一样莫队转移。
我还是用的是Sqrt(n)的子树分块，时间和空间都还比较充足！
P.S.这竟然一遍写出来好开心！第一次提交忘记去掉freopen了、、QAQ

代码

/*Author:WNJXYK*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int Maxn=100010;
const int MaxDep=20;
struct Edge{
    int v,nxt;
    Edge(){
    }
    Edge(int a,int b){
        v=a;nxt=b;
    }
};
Edge e[Maxn*2];
int nume;
int head[Maxn];
inline void addEdge(int x,int y){
    e[++nume]=Edge(x,head[y]);
    head[y]=nume;
    e[++nume]=Edge(y,head[x]);
    head[x]=nume;
}
struct Query{
    int a,b;
    int index;
    int time;
    Query(){}
    Query(int a0,int b0,int index0,int time0){
        a=a0;b=b0;
        index=index0;
        time=time0;
    }
};
Query qst[Maxn*2];
struct Change{
    int x,y,pre;
    Change(){}
    Change(int a,int b,int c){
        x=a;y=b;pre=c;
    }
};
Change cag[Maxn*2];
int qsts,cags;
int n,m,q;
int root;
int dep[Maxn],pre[Maxn],fa[Maxn][MaxDep],hom[Maxn],col[Maxn],sum[Maxn],stack[Maxn];
long long num[Maxn],val[Maxn],w[Maxn];
int preCol[Maxn];
bool visited[Maxn];
int dfn,cnt,tp;
int sqtn;
long long res[Maxn];
long long Ans;
int dfs(int x,int depth){
    visited[x]=true;
    pre[x]=++dfn;
    dep[x]=depth;
    int siz=0;
    for (int i=1;i<MaxDep;i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].v;
        if (!visited[v]){
            fa[v][0]=x;
            siz+=dfs(v,dep[x]+1);
            if (siz>sqtn){
                cnt++;
                for (int k=1;k<=siz;k++) hom[stack[tp--]]=cnt;
                siz=0;
            }
        }
    }
    stack[++tp]=x;
    return siz+1;
}
inline void swap(int &a,int &b){
    int tmp=a;
    a=b;
    b=tmp;
}
inline void swim(int &x,int h){
    for (int i=0;h>0;i++){
        if (h&1) x=fa[x][i];
        h/=2;
    }
}
inline int getLca(int x,int y){
    if (dep[x]>dep[y]) swap(x,y);
    swim(y,dep[y]-dep[x]);
    if (x==y) return x;
    for (int i=0;;){
        for (i=0;fa[x][i]!=fa[y][i];i++);
        if (i==0) return fa[x][i];
        x=fa[x][i-1];y=fa[y][i-1];
    }
}
inline bool cmp(Query a,Query b){
    if (hom[a.a]<hom[b.a]) return true;
    if (hom[a.a]==hom[b.a] && pre[a.b]<pre[b.b]) return true;
    return false;
}
inline void reverse(int x){
    if (visited[x]){
        visited[x]=false;
        Ans-=(long long)w[num[col[x]]]*(long long)val[col[x]];
        num[col[x]]--;
    }else{
        visited[x]=true;
        num[col[x]]++;
        Ans+=(long long)w[num[col[x]]]*(long long)val[col[x]];
    }
}
inline void solve(int x,int y,int lca){
    while(x!=lca){
        reverse(x);
        x=fa[x][0];
    }
    while(y!=lca){
        reverse(y);
        y=fa[y][0];
    }
}
inline void change(int x,int val){
    if (visited[x]){
        reverse(x);
        col[x]=val;
        reverse(x);
    }else{
        col[x]=val;
    }
}
int main(){
    //freopen("park.in","r",stdin);
    //freopen("park.out","w",stdout);
    scanf("%d%d%d",&n,&m,&q);
    while(sqtn*sqtn<=n) sqtn++;
    for (int i=1;i<=m;i++) scanf("%lld",&val[i]);
    for (int i=1;i<=n;i++) scanf("%lld",&w[i]);
    for (int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        addEdge(x,y);
    }
    root=1;
    fa[root][0]=root;
    dfs(root,1);
    cnt++;
    while(tp>0) hom[stack[tp--]]=cnt;
    for (int i=1;i<=n;i++) scanf("%d",&col[i]);
    for (int i=1;i<=n;i++) preCol[i]=col[i];
    for (int i=1;i<=q;i++){
        int t,a,b;
        scanf("%d%d%d",&t,&a,&b);
        if (t==0){
            cag[++cags]=Change(a,b,preCol[a]);
            preCol[a]=b;
        }else{
            if (pre[a]>pre[b]) swap(a,b);
            qst[++qsts]=Query(a,b,qsts,cags);
        }
    }
    sort(qst+1,qst+qsts+1,cmp);
    memset(visited,false,sizeof(visited));
    Ans=0;
    for (int i=1;i<=qst[1].time;i++) change(cag[i].x,cag[i].y);
    int lca=getLca(qst[1].a,qst[1].b);
    solve(qst[1].a,qst[1].b,lca);
    reverse(lca);
    res[qst[1].index]=Ans;
    reverse(lca);
    for (int i=2;i<=qsts;i++){
        for (int j=qst[i-1].time;j<=qst[i].time;j++) change(cag[j].x,cag[j].y);
        for (int j=qst[i-1].time;j>qst[i].time;j--) change(cag[j].x,cag[j].pre);
        int lca=getLca(qst[i].a,qst[i].b);
        solve(qst[i-1].a,qst[i].a,getLca(qst[i-1].a,qst[i].a));
        solve(qst[i-1].b,qst[i].b,getLca(qst[i-1].b,qst[i].b));
        reverse(lca);
        res[qst[i].index]=Ans;
        reverse(lca);
    }
    for (int i=1;i<=qsts;i++) printf("%lldn",res[i]);
    return 0;
}

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

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

/*Author:WNJXYK*/

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int Maxn=100010;

const int MaxDep=20;

struct Edge{

int v,nxt;

Edge(){

}

Edge(int a,int b){

v=a;nxt=b;

}

};

Edge e[Maxn*2];

int nume;

int head[Maxn];

inline void addEdge(int x,int y){

e[++nume]=Edge(x,head[y]);

head[y]=nume;

e[++nume]=Edge(y,head[x]);

head[x]=nume;

}

struct Query{

int a,b;

int index;

int time;

Query(){}

Query(int a0,int b0,int index0,int time0){

a=a0;b=b0;

index=index0;

time=time0;

}

};

Query qst[Maxn*2];

struct Change{

int x,y,pre;

Change(){}

Change(int a,int b,int c){

x=a;y=b;pre=c;

}

};

Change cag[Maxn*2];

int qsts,cags;

int n,m,q;

int root;

int dep[Maxn],pre[Maxn],fa[Maxn][MaxDep],hom[Maxn],col[Maxn],sum[Maxn],stack[Maxn];

long long num[Maxn],val[Maxn],w[Maxn];

int preCol[Maxn];

bool visited[Maxn];

int dfn,cnt,tp;

int sqtn;

long long res[Maxn];

long long Ans;

int dfs(int x,int depth){

visited[x]=true;

pre[x]=++dfn;

dep[x]=depth;

int siz=0;

for (int i=1;i<MaxDep;i++)

fa[x][i]=fa[fa[x][i-1]][i-1];

for (int i=head[x];i;i=e[i].nxt){

int v=e[i].v;

if (!visited[v]){

fa[v][0]=x;

siz+=dfs(v,dep[x]+1);

if (siz>sqtn){

cnt++;

for (int k=1;k<=siz;k++) hom[stack[tp--]]=cnt;

siz=0;

}

stack[++tp]=x;

return siz+1;

}

inline void swap(int &a,int &b){

int tmp=a;

a=b;

b=tmp;

}

inline void swim(int &x,int h){

for (int i=0;h>0;i++){

if (h&1) x=fa[x][i];

h/=2;

}

inline int getLca(int x,int y){

if (dep[x]>dep[y]) swap(x,y);

swim(y,dep[y]-dep[x]);

if (x==y) return x;

for (int i=0;;){

for (i=0;fa[x][i]!=fa[y][i];i++);

if (i==0) return fa[x][i];

x=fa[x][i-1];y=fa[y][i-1];

}

inline bool cmp(Query a,Query b){

if (hom[a.a]<hom[b.a]) return true;

if (hom[a.a]==hom[b.a] && pre[a.b]<pre[b.b]) return true;

return false;

}

inline void reverse(int x){

if (visited[x]){

visited[x]=false;

Ans-=(long long)w[num[col[x]]]*(long long)val[col[x]];

num[col[x]]--;

}else{

visited[x]=true;

num[col[x]]++;

Ans+=(long long)w[num[col[x]]]*(long long)val[col[x]];

}

inline void solve(int x,int y,int lca){

while(x!=lca){

reverse(x);

x=fa[x][0];

}

while(y!=lca){

reverse(y);

y=fa[y][0];

}

inline void change(int x,int val){

if (visited[x]){

reverse(x);

col[x]=val;

reverse(x);

}else{

col[x]=val;

}

int main(){

//freopen("park.in","r",stdin);

//freopen("park.out","w",stdout);

scanf("%d%d%d",&n,&m,&q);

while(sqtn*sqtn<=n) sqtn++;

for (int i=1;i<=m;i++) scanf("%lld",&val[i]);

for (int i=1;i<=n;i++) scanf("%lld",&w[i]);

for (int i=1;i<n;i++){

int x,y;

scanf("%d%d",&x,&y);

addEdge(x,y);

}

root=1;

fa[root][0]=root;

dfs(root,1);

cnt++;

while(tp>0) hom[stack[tp--]]=cnt;

for (int i=1;i<=n;i++) scanf("%d",&col[i]);

for (int i=1;i<=n;i++) preCol[i]=col[i];

for (int i=1;i<=q;i++){

int t,a,b;

scanf("%d%d%d",&t,&a,&b);

if (t==0){

cag[++cags]=Change(a,b,preCol[a]);

preCol[a]=b;

}else{

if (pre[a]>pre[b]) swap(a,b);

qst[++qsts]=Query(a,b,qsts,cags);

}

sort(qst+1,qst+qsts+1,cmp);

memset(visited,false,sizeof(visited));

Ans=0;

for (int i=1;i<=qst[1].time;i++) change(cag[i].x,cag[i].y);

int lca=getLca(qst[1].a,qst[1].b);

solve(qst[1].a,qst[1].b,lca);

reverse(lca);

res[qst[1].index]=Ans;

reverse(lca);

for (int i=2;i<=qsts;i++){

for (int j=qst[i-1].time;j<=qst[i].time;j++) change(cag[j].x,cag[j].y);

for (int j=qst[i-1].time;j>qst[i].time;j--) change(cag[j].x,cag[j].pre);

int lca=getLca(qst[i].a,qst[i].b);

solve(qst[i-1].a,qst[i].a,getLca(qst[i-1].a,qst[i].a));

solve(qst[i-1].b,qst[i].b,getLca(qst[i-1].b,qst[i].b));

reverse(lca);

res[qst[i].index]=Ans;

reverse(lca);

}

for (int i=1;i<=qsts;i++) printf("%lldn",res[i]);

return 0;

}

WNJXYKの博客

喂你脚下有坑