danihao123's Blog

[LibreOJ 2135][ZJOI2015]幻想乡战略游戏

竟然1A了蛤蛤蛤蛤蛤

这题用人话说就是给你一个不会动的树，让你求带权重心。

先解决一个问题：如果要求动态修改点权，并且要求多次询问求某点 $x$ 的 $\sum_{i = 1}^n d_i\cdot dist(i, x)$ ，怎么做？

很显然对于一个点 $x$ ，对它造成贡献的点，可能是在以 $x$ 为根的点分子树里的，也可能在 $x$ 之外。但是一个不在该点分子树内的点要对 $x$ 产生贡献，必须要经过 $x$ 在分治树上的祖先。

所以我们可以考虑对每个重心，记录下它这个点分子树中所有点对该重心的贡献、对点分树上的父亲的贡献以及该点分子树的点权和。每次求答案时 $x$ 所在的分治子树的贡献很好考虑，那考虑一下其分治树上祖先对 $x$ 的贡献就行了。

那带权重心怎么求呢？如果我们把树的根变成带权重心，那么我们会发现越远离根则答案越劣。所以我们如果只往使得答案更小的地方走，那么最后一定会走到带权重心上。

我们考虑把这个过程放点分树上。从整棵树的重心开始往下走，每次如果发现有一条出边指向的点答案更好，那就往这个子结构（不是指向的点而是那个联通块的重心，否则时间复杂度不对）里走。最后走不动了，走到的点就是带权重心了。

求LCA我用的是 $O(logn)$ 的树剖而不是 $O(1)$ 搞法，但是跑的贼快（可能和树剖常数小有关？）。

吐槽一点，原题提到了每个点的度数不超过20，但是网上几乎所有OJ上该题的题面都没提到这一点……

代码：

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

186

187

188

189

190

191

192

193

194

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <set>
#include <vector>
#include <queue>
#include <stack>
typedef long long ll;
const int maxn = 100005;
const int maxe = maxn << 1;
int first[maxn];
int next[maxe], to[maxe];
ll dist[maxe];
void add_edge(int u, int v, ll d) {
  static int cnt = 0;
  cnt ++;
  next[cnt] = first[u];
  first[u] = cnt;
  to[cnt] = v;
  dist[cnt] = d;
}
  
int n;
int size[maxn], hson[maxn], fa[maxn], dep[maxn];
ll dis[maxn];
void dfs_1(int x, int father = 0, int depth = 1, ll d = 0) {
  size[x] = 1;
  fa[x] = father;
  dep[x] = depth;
  dis[x] = d;
  int max_siz = 0;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(v != father) {
      dfs_1(v, x, depth + 1, d + dist[i]);
      size[x] += size[v];
      if(size[v] > max_siz) {
        max_siz = size[v];
        hson[x] = v;
      }
    }
  }
}
int dfn[maxn], top[maxn], tid[maxn];
void dfs_2(int x, int father = 0, int a = 1) {
  static int dfn_clk = 0;
  dfn[x] = ++ dfn_clk;
  tid[dfn[x]] = x;
  top[x] = a;
  if(!hson[x]) {
    return;
  } else {
    dfs_2(hson[x], x, a);
  }
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(v != father && v != hson[x]) {
      dfs_2(v, x, v);
    }
  }
}
int lca(int x, int y) {
  while(top[x] != top[y]) {
    if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
    x = fa[top[x]];
  }
  if(dep[x] > dep[y]) {
    return y;
  } else {
    return x;
  }
}
ll calc_dist(int x, int y) {
  int l = lca(x, y);
  return dis[x] + dis[y] - 2LL * dis[l];
}
 
bool vis[maxn];
int siz[maxn];
void gen_siz(int x, int f = 0) {
  siz[x] = 1;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v] && v != f) {
      gen_siz(v, x);
      siz[x] += siz[v];
    }
  }
}
int nrt, rt;
void gen_rt(int x, int f = 0) {
  bool flag = (siz[x] * 2 >= siz[nrt]);
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v] && v != f) {
      flag = (flag && (siz[v] * 2 <= siz[nrt]));
      gen_rt(v, x);
    }
  }
  if(flag) rt = x;
}
ll w[maxn];
int crt, cfa[maxn];
ll pans[maxn], give[maxn], sumv[maxn];
int point2[maxe];
/*
void search_p(int x, std::stack<int> *V, int f = 0) {
  V -> push(x);
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v] && v != f) {
      search_p(v, V, x);
    }
  }
}
*/
int divide(int x) {
  nrt = rt = x;
  gen_siz(x); gen_rt(x);
  x = rt; vis[x] = true;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v]) {
      int ch = divide(v);
      point2[i] = ch;
      cfa[ch] = x;
    }
  }
  return x;
}
void update(int x, ll delta) {
  int p = x;
  while(p) {
    pans[p] += delta * calc_dist(p, x);
    if(p != crt) give[p] += delta * calc_dist(x, cfa[p]);
    sumv[p] += delta;
    p = cfa[p];
  }
}
ll get_ans(int x) {
  ll ans = pans[x];
  int p = x;
  while(p != crt) {
    int f = cfa[p];
    ans += pans[f] - give[p];
    ans += calc_dist(x, f) * (sumv[f] - sumv[p]);
    p = cfa[p];
  }
  return ans;
}
ll get_best() {
  int p = crt;
  std::stack<int> S;
  ll now_ans;
  while(true) {
    S.push(p); vis[p] = true;
    bool fix = true;
    now_ans = get_ans(p);
    for(int i = first[p]; i; i = next[i]) {
      int v = to[i];
      if(vis[v]) continue;
      if(get_ans(v) < now_ans) {
        fix = false;
        p = point2[i];
        break;
      }
    }
    if(fix) break;
  }
  while(!S.empty()) {
    int u = S.top(); S.pop();
    vis[u] = false;
  }
  return now_ans;
}
 
int main() {
  int q; scanf("%d%d", &n, &q);
  for(int i = 0; i < n - 1; i ++) {
    int u, v; ll d; scanf("%d%d%lld", &u, &v, &d);
    add_edge(u, v, d); add_edge(v, u, d);
  }
  dfs_1(1); dfs_2(1);
  crt = divide(1); memset(vis, 0, sizeof(vis));
  while(q --) {
    int u, e; scanf("%d%d", &u, &e);
    update(u, e);
    printf("%lld\n", get_best());
  }
  return 0;
}

[BZOJ 1095][ZJOI2007]Hide 捉迷藏

蛤蛤蛤我这题终于调出来了~~~（然后1A了）~~

点分树处女作。其实点分树的思想并不难理解，就是把点分的过程抽象化到一棵树上。

其实唯一比较烦人的就是点分树上的儿子给父亲的贡献要开一个堆处理……非常烦人。

代码（其中有海量本来拿来调试的代码，慎读）：

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

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

/**************************************************************
    Problem: 1095
    User: danihao123
    Language: C++
    Result: Accepted
    Time:15268 ms
    Memory:128944 kb
****************************************************************/
  
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <set>
#include <vector>
#include <queue>
const int maxn = 100005;
const int maxe = maxn << 1;
int first[maxn];
int next[maxe], to[maxe];
void add_edge(int u, int v) {
  static int cnt = 0;
  cnt ++;
  next[cnt] = first[u];
  first[u] = cnt;
  to[cnt] = v;
}
  
int size[maxn], hson[maxn], fa[maxn], dep[maxn];
void dfs_1(int x, int father = 0, int depth = 1) {
  size[x] = 1;
  fa[x] = father;
  dep[x] = depth;
  int max_siz = 0;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(v != father) {
      dfs_1(v, x, depth + 1);
      size[x] += size[v];
      if(size[v] > max_siz) {
        max_siz = size[v];
        hson[x] = v;
      }
    }
  }
}
int dfn[maxn], top[maxn], tid[maxn];
void dfs_2(int x, int father = 0, int a = 1) {
  static int dfn_clk = 0;
  dfn[x] = ++ dfn_clk;
  tid[dfn[x]] = x;
  top[x] = a;
  if(!hson[x]) {
    return;
  } else {
    dfs_2(hson[x], x, a);
  }
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(v != father && v != hson[x]) {
      dfs_2(v, x, v);
    }
  }
}
int lca(int x, int y) {
  while(top[x] != top[y]) {
    if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
    x = fa[top[x]];
  }
  if(dep[x] > dep[y]) {
    return y;
  } else {
    return x;
  }
}
  
bool vis[maxn];
int siz[maxn];
void gen_siz(int x, int fa = 0) {
  siz[x] = 1;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v] && v != fa) {
      gen_siz(v, x);
      siz[x] += siz[v];
    }
  }
}
int nrt, rt;
void gen_rt(int x, int fa = 0) {
  bool ok = (2 * siz[x] >= siz[nrt]);
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v] && v != fa) {
      ok = ok && (2 * siz[v] <= siz[nrt]);
      gen_rt(v, x);
    }
  }
  if(ok) rt = x;
}
int crt;
int cfa[maxn];
typedef std::priority_queue<int> heap;
struct dheap {
  heap Q, D;
  void push(int x) {
    Q.push(x);
  }
  void pop() {
    while(!D.empty() && Q.top() == D.top()) {
#ifdef DEBUG
      printf("deleting %d\n", D.top());
#endif
      Q.pop(); D.pop();
    }
    Q.pop();
  }
  int top() {
    while(!D.empty() && Q.top() == D.top()) {
#ifdef DEBUG
      printf("deleting %d\n", D.top());
#endif
      Q.pop(); D.pop();
    }
    return Q.top();
  }
  void del(int x) {
    D.push(x);
  }
  size_t size() {
    return Q.size() - D.size();
  }
  int sec() {
    int fir = top(); pop();
    int ret = top(); push(fir);
    return ret;
  }
};
dheap all;
dheap Q[maxn], sg[maxn];
int divide(int x) {
  nrt = rt = x;
  gen_siz(x); gen_rt(x);
  x = rt; vis[x] = true;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v]) {
      cfa[divide(v)] = x;
    }
  }
  return x;
}
int n;
int get_ans(dheap &q) {
  return q.top() + q.sec();
}
bool sta[maxn];
int dist(int x, int y) {
  int ret = dep[x] + dep[y] - 2 * dep[lca(x, y)];
#ifdef DEBUG
  printf("dist(%d, %d) : %d\n", x, y, ret);
#endif
  return ret;
}
void light_on(int p) {
  sta[p] = true;
  int x = p;
  int og = -1, ng = 0;
  while(x) {
    int old_ans = -1, old_sg = -1;
    if(Q[x].size() > 1) {
      old_ans = get_ans(Q[x]);
    }
    if(sg[x].size() > 0) {
      old_sg = sg[x].top();
    }
    if(og != -1) Q[x].del(og);
    if(ng != -1) Q[x].push(ng);
    if(Q[x].size() > 1) all.push(get_ans(Q[x]));
    if(old_ans != -1) all.del(old_ans);
    if(cfa[x] != 0) {
      og = old_sg;
      sg[x].push(dist(p, cfa[x]));
      ng = sg[x].top();
    }
    x = cfa[x];
  }
}
void light_off(int p) {
  sta[p] = false;
  int x = p;
  int og = 0, ng = -1;
  while(x) {
    int old_ans = -1, old_sg = -1;
    if(Q[x].size() > 1) old_ans = get_ans(Q[x]);
    if(sg[x].size() > 0) {
      old_sg = sg[x].top();
    }
    if(og != -1) Q[x].del(og);
    if(ng != -1) Q[x].push(ng);
#ifdef DEBUG
    printf("%d deleting %d\n", x, og);
#endif
    if(Q[x].size() > 1) all.push(get_ans(Q[x]));
    if(old_ans != -1) all.del(old_ans);
#ifdef DEBUG
    int tmp = -1;
    if(Q[x].size() > 1) tmp = get_ans(Q[x]);
    printf("ans of %d : %d -> %d\n", x, old_ans, tmp);
#endif
    if(cfa[x] != 0) {
      og = old_sg;
      sg[x].del(dist(p, cfa[x]));
      if(sg[x].size() > 0) {
        ng = sg[x].top();
      } else {
        ng = -1;
      }
    }
    x = cfa[x];
  }
}
void print_dheap(dheap &q) {
  std::vector<int> V;
  while(q.size() > 0) {
    int t = q.top(); q.pop();
    printf("%d ", t);
    V.push_back(t);
  }
  puts("");
  for(int i = 0; i < V.size(); i ++) {
    q.push(V[i]);
  }
}
  
int main() {
  scanf("%d", &n);
  for(int i = 1; i <= n - 1; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    add_edge(u, v); add_edge(v, u);
  }
  dfs_1(1); dfs_2(1);
#ifdef DEBUG
  for(int i = 1; i <= n; i ++) {
    printf("%d top fa hson : %d %d %d\n", i, top[i], fa[i], hson[i]);
  }
#endif 
  crt = divide(1);
#ifdef DEBUG
  printf("crt id %d\n", crt);
  for(int i = 1; i <= n; i ++) {
    printf("cfa[%d] : %d\n", i, cfa[i]);
  }
#endif
  int num = 0;
  for(int i = 1; i <= n; i ++) {
    light_on(i); num ++;
#ifdef DEBUG
    printf("heap while inserting %d : ", i);
    print_dheap(all);
#endif
  }
  int q; scanf("%d", &q);
  while(q --) {
    char op[3]; scanf("%s", op);
    if(op[0] == 'G') {
      if(num == 0) {
        puts("-1");
      } else if(num == 1) {
        puts("0");
      } else {
        printf("%d\n", all.top());
      }
    } else {
      int i; scanf("%d", &i);
      if(sta[i]) {
        light_off(i);
        num --;
      } else {
        light_on(i);
        num ++;
      }
    }
#ifdef DEBUG
    print_dheap(all);
#endif
  }
  return 0;
}

[LibreOJ 2135][ZJOI2015]幻想乡战略游戏

[BZOJ 1095][ZJOI2007]Hide 捉迷藏

danihao123

搜索

分类

标签云

最新评论

最新留言

神犇的Blog

RSS

功能

计数器