Link51nod 1470Sol不错的题目拿到题目感觉没啥想法，但是仔细想想，会发现切入点应该是什么样的边如何影响有没有解。假如有一个环，定向以后仍然环上的点仍然可以互相到达。那么环是我们可以不需要考虑合不合法的因素。推广一下，在一个 e-DDC 中的点给边定向以后也是都可以互相到达的。因此，可以先对原图进行 e-DDC 缩边，得到了一棵原图中桥组成的树。现在影响是否有解的只有这棵树上的边了。相当于我们要给树边定向。我们钦定对于一个限制 $(s, t)$，$p$ 为 $s,t$ 对应的 e-DDC 的树上结点的 LCA。从 $s \to p$ 的为正向，从 $v \to p$ 的为反向。那么可以把 $s \to p$ 的路径上的点全部 $+1$，$t \to p$ 的全部 $-1$。只需要检查有没有一个点的权值为 $0$ 即可。如果你想多一个 $\log$，可以选择线段树。但是只需要树上差分就行了。Code#include <bits/stdc++.h> using namespace std; typedef vector < int > vec; const int SIZE = 5e5 + 5; int n, m, q, num = 1, tim, cnt, N; int head[SIZE], dfn[SIZE], low[SIZE], bri[SIZE], deg[SIZE], col[SIZE]; int dep[SIZE], idx[SIZE], bel[SIZE], fa[SIZE], siz[SIZE], son[SIZE], dif1[SIZE], dif2[SIZE]; struct node { int to, nxt; } edge[SIZE << 1]; vec g[SIZE]; namespace GTR { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } inline int read() { int a = 0, b = 1, c = fetch(); while (c < 48 || c > 57) b ^= c == '-', c = fetch(); while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch(); return b ? a : -a; } } using GTR::read; void addEdge(int u, int v) { edge[++ num] = (node) {v, head[u]}, head[u] = num; } void dfs(int u, int p) { dfn[u] = low[u] = ++ tim; for (int i = head[u], v; i; i = edge[i].nxt) { v = edge[i].to; if (!dfn[v]) { dfs(v, i); low[u] = std::min(low[u], low[v]); if (low[v] > dfn[u]) bri[i] = bri[i ^ 1] = 1; } else if (i != (p ^ 1)) low[u] = std::min(low[u], dfn[v]); } } void ddc(int u) { col[u] = cnt; for (int i = head[u], v; i; i = edge[i].nxt) { v = edge[i].to; if (col[v] || bri[i]) continue; ddc(v); } } void dfs0(int u, int anc) { siz[u] = 1, idx[u] = N; for (int v: g[u]) { if (v == anc) continue; fa[v] = u, dep[v] = dep[u] + 1; dfs0(v, u); siz[u] += siz[v]; if (siz[son[u]] < siz[v]) son[u] = v; } } void dfs1(int u, int top) { bel[u] = top; if (son[u]) dfs1(son[u], top); for (int v: g[u]) { if (v == son[u] || v == fa[u]) continue; dfs1(v, v); } } int lca(int u, int v) { while (bel[u] ^ bel[v]) { if (dep[bel[u]] < dep[bel[v]]) std::swap(u, v); u = fa[bel[u]]; } return dep[u] < dep[v] ? u : v; } int judge(int u) { for (int v: g[u]) { if (v == fa[u]) continue; if (!judge(v) || (dif1[v] && dif2[v])) return 0; dif1[u] += dif1[v], dif2[u] += dif2[v]; } return 1; } int main() { // freopen("code.in", "r", stdin); n = read(), m = read(), q = read(); for (int i = 1, u, v; i <= m; ++ i) { u = read(), v = read(); addEdge(u, v), addEdge(v, u); } for (int i = 1; i <= n; ++ i) if (!dfn[i]) dfs(i, 0); for (int i = 1; i <= n; ++ i) { if (!col[i]) { ++ cnt; ddc(i); } } for (int u = 1; u <= n; ++ u) { for (int i = head[u], v; i; i = edge[i].nxt) { v = edge[i].to; if (col[u] < col[v]) { g[col[u]].emplace_back(col[v]), g[col[v]].emplace_back(col[u]); } } } for (int i = 1; i <= cnt; ++ i) { if (!idx[i]) { dep[i] = 0, fa[i] = 0, idx[i] = ++ N; dfs0(i, 0), dfs1(i, 1); } } for (int i = 1, u, v; i <= q; ++ i) { u = col[read()], v = col[read()]; if (u == v) continue; if (idx[u] != idx[v]) return puts("No"), 0; int par = lca(u, v); -- dif1[par], -- dif2[par]; ++ dif1[u], ++ dif2[v]; } for (int i = 1; i <= cnt; ++ i) { if (dep[i] == 0 && !judge(i)) return puts("No"), 0; } puts("Yes"); return 0; }
问题引入给定一棵 $n$ 个点的树，求以每个点为根的子树的重心。数据范围：$n \leq 2 \times 10^5$朴素方法$O(n^2)$ 对每个点求出重心，时间无法承受。方法一考虑到重心的性质：一个子树的重心一定在其根节点所在重链上。发现重心的定义等价于重心的最大子树不超过整棵子树的一半，因此直接在重链上向下倍增即可。时间复杂度：$O(n \log n)$代码：int get(int x, int rt) { return std::max(siz[rt] - siz[x], siz[son[x]]); } void dfs1(int u) { if (siz[son[u]] <= siz[u] / 2) tag[ctr[u] = u] = 1; for (int i = head[u], v; i; i = edge[i].nxt) { v = edge[i].to; if (v == fa[u]) continue; dfs1(v); int c = ctr[v]; if (ctr[u] || siz[v] <= siz[u] / 2) continue; while (fa[c] && get(c, u) > siz[u] / 2) c = fa[c]; while (fa[c] && get(fa[c], u) <= siz[u] / 2) c = fa[c]; tag[ctr[u] = c] = 1; } }方法二还想再优秀一点？试图求得 $O(n)$ 的做法。有一个假的结论，可以让你爆零：重心只有可能是儿子的重心、儿子重心的父亲和它自己。在这些点组成的可能集合中找子树大小最大的。还有一个假的结论：重链上连续的一段节点的重心也是该重链上连续的一段节点。这两个结论为什么假掉了，我们可以构造一棵树，使得存在点不是任何子树的重心。如图：例如在一个应用中，每次修改的点都是重心。其中标黄的边为重边,未标黄的为轻边。如果我们更新重链上连续的一段：1,2,4。那么对应的需要修改的重心为 1,4。并不是连续的一段。所以上述结论是假的。稍微将这个结论换一下就真了：即对于任意节点 $u$ ,以它为重心的节点一定和 $u$ 在同一条重链上并且为连续的一段。有了这个结论，结合重链的性质：$\sum$ 重链长度 是 $O(n)$ 级别的，我们可以找到 $O(n)$ 做法。以 20210923 CDQZ NOIp模拟赛中秋特别版 T2为例，代码如下：（by CJ_wyz)#include<cstdio> #include<cctype> #include<set> #include<ctime> #include<cmath> #include<queue> #include<vector> #include<bitset> #include<random> #include<cstring> #include<cstdlib> #include<algorithm> #define mp std::make_pair #define swap std::swap #define lowbit(k) (k&(-k)) #define mod 31607 template<class T> inline T read(){ T r=0,f=0; char c; while(!isdigit(c=getchar()))f|=(c=='-'); while(isdigit(c))r=(r<<1)+(r<<3)+(c^48),c=getchar(); return f?-r:r; } template<class T> inline T min(T a,T b){ return a<b?a:b; } template<class T> inline T max(T a,T b){ return a>b?a:b; } #define ll long long inline ll gcd(ll a,ll b){ return b?gcd(b,a%b):a; } inline ll lcm(ll a,ll b){ return a/gcd(a,b)*b; } inline ll qpow(ll a,int b){ ll ans=1; for(;b;b>>=1){ if(b&1)(ans*=a)%=mod; (a*=a)%=mod; } return ans; } #undef ll struct Z{ #define add(x) (x>=mod?x-mod:x) #define sub(x) (x<0?x+mod:x) int x; inline int val() const{ return x; } inline int inv() const{ return qpow(x,mod-2); } Z(int x=0):x(x) {} Z operator -() const{ return Z(add(mod-x)); } Z &operator +=(const Z &z){ x=add(x+z.x); return *this; } Z &operator -=(const Z &z){ x=sub(x-z.x); return *this; } Z &operator *=(const Z &z){ x=1ll*x*z.x%mod; return *this; } Z &operator /=(const Z &z){ x=1ll*x*z.inv()%mod; return *this; } Z operator +(const Z &z) const{ return Z(add(x+z.x)); } Z operator -(const Z &z) const{ return Z(sub(x-z.x)); } Z operator *(const Z &z) const{ return Z(1ll*x*z.x%mod); } Z operator /(const Z &z) const{ return Z(1ll*x*z.inv()%mod); } #undef add #undef sub }; #define maxn 202202 struct E{ int v,nxt; E() {} E(int v,int nxt):v(v),nxt(nxt) {} }e[maxn<<1]; int n,s_e,head[maxn],ct[maxn]; inline void a_e(int u,int v){ e[++s_e]=E(v,head[u]); head[u]=s_e; } int L[maxn],R[maxn]; std::vector<int> d[maxn]; namespace T_C{ int s_dfn,fa[maxn],dfn[maxn],dep[maxn],size[maxn]; int N,low[maxn],down[maxn],top[maxn],son[maxn]; void dfs1(int u){ size[u]=1; dep[u]=dep[fa[u]]+1; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].v; if(size[v])continue; fa[v]=u,dfs1(v); size[u]+=size[v]; if(size[son[u]]<size[v])son[u]=v; } } void dfs2(int u,int t){ top[u]=t; dfn[u]=++s_dfn; d[t].push_back(u); if(!son[u]){ R[u]=s_dfn; return; } dfs2(son[u],t); for(int i=head[u];i;i=e[i].nxt){ int v=e[i].v; if(top[v])continue; dfs2(v,v); } } namespace BIT{ long long c[2][maxn]; inline void add(int k,int x){ for(int p=k;k<=N;k+=lowbit(k)) c[0][k]+=x,c[1][k]+=1ll*p*x; } inline long long ask(int k){ long long sum=0; for(int x=k;k;k^=lowbit(k)) sum+=(x+1)*c[0][k]-c[1][k]; return sum; } inline void add(int l,int r,int v){ add(l,v),add(r+1,-v); } inline long long ask(int l,int r){ return ask(r)-ask(l-1); } } inline void change(int u,int v,int val){ int fu=top[u],fv=top[v]; while(fu^fv){ if(dep[fu]<dep[fv]) swap(u,v),swap(fu,fv); BIT::add(low[ct[fu]],low[ct[u]],val); u=fa[fu],fu=top[u]; } if(dep[u]>dep[v])swap(u,v); BIT::add(low[ct[u]],low[ct[v]],val); } inline long long ask1(int u,int v){ long long sum=0; int fu=top[u],fv=top[v]; while(fu^fv){ if(dep[fu]<dep[fv]) swap(u,v),swap(fu,fv); if(down[fu]<=low[u]) sum+=BIT::ask(down[fu],low[u]); u=fa[fu],fu=top[u]; } if(dep[u]>dep[v])swap(u,v); if(down[u]<=low[v]) sum+=BIT::ask(down[u],low[v]); return sum; } inline long long ask2(int u){ return L[u]?BIT::ask(L[u],R[u]):0; } bool in[maxn]; void dfs3(int u){ if(in[u])low[u]=++N; if(!son[u]){ L[u]=R[u]=low[u]?low[u]:0; return; } dfs3(son[u]); L[u]=low[u]?low[u]:L[son[u]]; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].v; if((v^fa[u])&&(v^son[u])) dfs3(v); } R[u]=N; } inline void init(){ dfs1(1); dfs2(1,1); for(int t=1;t<=n;t++){ if(!d[t].size())continue; ct[d[t].back()]=d[t].back(); in[d[t].back()]=1; for(int i=d[t].size()-2;~i;i--){ int u=d[t][i]; ct[u]=ct[d[t][i+1]]; while(size[ct[u]]<=size[u]/2) ct[u]=fa[ct[u]]; in[ct[u]]=1; } } dfs3(1); for(int t=1;t<=n;t++){ if(!d[t].size())continue; down[d[t].back()]=low[d[t].back()]; for(int i=d[t].size()-2;~i;i--){ int u=d[t][i]; down[u]=low[u]?low[u]:down[d[t][i+1]]; } for(int i=1;i<(int)d[t].size();i++){ int u=d[t][i]; low[u]=low[u]?low[u]:low[d[t][i-1]]; } } } } inline void work(){ int opt=read<int>(); int u=read<int>(); if(opt==2){ printf("%lld\n",T_C::ask2(u)); return; } int v=read<int>(); if(opt==1)T_C::change(u,v,read<int>()); else printf("%lld\n",T_C::ask1(u,v)); } int main(){ n=read<int>(); for(int i=1;i<n;i++){ int u=read<int>(); int v=read<int>(); a_e(u,v),a_e(v,u); } T_C::init(); int t=read<int>(); while(t--)work(); return 0; }
Link中文题面链接Sol先来考虑一个简单版本的问题：我们只有一个北国银行。答案是：$$ \sum\limits_{(x,fa)\in E} w \cdot min(size_{x},S - size_{x}) $$证明：不妨设树根为$1$。在上面的表达式中，$size_{x}$ 表示的是在 $x$ 子树中居民的数量，$S$表示树中居民的总数量。考虑如何计算所有居民接收到一枚钟离盾的总时间：对于每一条边，它的贡献为 $w$ $*$ 通过这条边的居民的数量的总和，即对于每一条边 $(x, fa, w)$，我们有两种选择：一是选择子树内的所有居民通过该边（此时北国银行在子树外），故此部分贡献为 $w \cdot size_{x}$；二是选择 $x$ 的子树外的所有点上的居民通过该边进入 $x$ 的子树领取钟离盾（此时北国银行在子树内）。两种方式取 $min$ 即可。考虑最终北国银行放置的位置，会有一条没有居民过的边。那么可以枚举该边并将此边断开，使原树分成两个树，再通过上面的方法对两棵树的答案独立计算。时间复杂度为 $O(n^2)$。定义 $in_v$ 为 DFS 时进入$v$ 点的时间戳，$out_v$ 为 DFS 时离开 $v$ 点的时间戳。假设只放置一个北国银行，我们就应该找到对于所有边 $e(v, to, w)$ ：$\sum\limits_{e\in E} w \cdot min(size_{to}, S - size_{to})$ 的总和。考虑 $size_{to}$ 和 $S - size_{to}$ 什么时候会算到贡献里：$w \cdot min(size_{to}, S - size_{to})$ 为 $w \cdot size_{to}$ 当且仅当 $size_{to} \leq \frac{S}{2}$， 为 $w \cdot (S - size_{to})$ 当且仅当 $size_{to} > \frac{S}{2}$。回到 $O(n^2)$ 的解法。我们在 DFS 时在树中移去边 $(v, to, w)$ 。现在有两棵子树，大小分别为：$X = size_{to}, Y = size_{1} - size_{to}$。 考虑分别在 $X, Y$ 两棵树上解决问题。第一部分先计算 $to$ 子树中的点的答案： $w \cdot min(size_{to}, X - size_{to})$ 的值的和。我们可以计算出 $w \cdot size_{to} (\forall size_{to} \leq \frac{X}{2}) + w \cdot X (\forall size_{to} > \frac{X}{2}) - w \cdot size_{to} (\forall size_{to} > \frac{X}{2})$。剩余的部分就是要求出区间 $[l,r]$ 内所有数字 $\leq K$ 的和。可以把区间 $[in_{to}, out_{to}]$ 内的点的 $w$ 和 $w \cdot size_{to}$ 丢进两个树状数组，分别统计两类的答案即可。$to$ 的子树以外的部分做法也很类似。注意要将这些操作在区间 $[1, in_{to} - 1]$ 和 $[out_{to} + 1, n]$ 和子树 $Y$ 上完成。除了从根节点开始的链到 $v$ （ 包括 $to$ 的子树中的节点）。在这条链上 $size_u$ 单调递减，所以用双指针并且记录前缀和。可以减去我们要为 $\leq \frac{Y}{2}$ 计算的部分。同样对 $size_{1} - size_{u}$ 做这样的步骤。最后加上我们需要的 $> \frac{Y}{2}$ 的部分，这部分在这条链上递增。时间复杂度和空间复杂度均为 $O(n \log n)$ 。Code#include <bits/stdc++.h> using namespace std; typedef long long LL; const int SIZE = 5e4 + 5, SIZE_N = 2.5e5 + 5; const LL inf = 9e18; int n, rt, num, tim, tot; int head[SIZE], a[SIZE], dep[SIZE], f[SIZE][18], dfn[SIZE], id[SIZE], lg[SIZE], fx[SIZE], s[SIZE], b[SIZE]; LL S, siz[SIZE], y[SIZE], z[SIZE], ans[SIZE], c[SIZE], C[SIZE]; struct node { int to, v, nxt; } edge[SIZE << 1]; struct ask { int l, r, d; LL k, s; inline bool operator< (const ask &a) const { return k < a.k; } } q[SIZE * 3]; void addEdge(int u, int v, int d) { edge[++ num] = (node) {v, d, head[u]}, head[u] = num; } namespace GTR { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } inline int read() { int a = 0, b = 1, c = fetch(); while (c < 48 || c > 57) b ^= c == '-', c = fetch(); while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch(); return b ? a : -a; } } using GTR::read; namespace fenwick { #define lowbit(x) (x & (-x)) void modify(LL *bit, int pos, LL val) { for ( ; pos <= n; pos += lowbit(pos)) bit[pos] += val; } LL query(LL *bit, int pos) { LL ans = 0; for ( ; pos; pos -= lowbit(pos)) ans += bit[pos]; return ans; } LL query(LL *bit, int l, int r) { return l > r ? 0ll : query(bit, r) - query(bit, l - 1); } } ; void dfs(int u, int fa) { siz[u] = a[u], s[u] = 1, dfn[u] = ++ tim; for (int i = head[u], v; i; i = edge[i].nxt) { v = edge[i].to; if (v == fa) continue; dep[v] = dep[u] + 1, f[v][0] = u, b[v] = edge[i].v; for (int j = 1; j < 18; ++ j) f[v][j] = f[f[v][j - 1]][j - 1]; dfs(v, u); siz[u] += siz[v], s[u] += s[v]; } } void dfs1(int u, int fa) { for (int i = head[u], v; i; i = edge[i].nxt) { v = edge[i].to; if (v == fa) continue; y[v] = y[u] + b[v], z[v] = z[u] + 1ll * b[v] * siz[v]; dfs1(v, u); id[v] = ++ tot; q[tot] = (ask) {dfn[v] + 1, dfn[v] + s[v] - 1, tot, siz[v], 0ll}; q[++ tot] = (ask) {1, dfn[v] - 1, tot, S - siz[v], 0ll}; q[++ tot] = (ask) {dfn[v] + s[v], n, tot, S - siz[v], 0ll}; int x = v; LL t = (S - siz[v]) >> 1; for (int j = lg[dep[v] - 1]; ~j; -- j) { if (f[x][j] && siz[f[x][j]] <= t) x = f[x][j]; } ans[v] = (z[f[x][0]] << 1) - z[u] - y[f[x][0]] * (S - siz[v]); x = v; t = ((S - siz[v]) >> 1) + siz[v]; for (int j = lg[dep[v] - 1]; ~j; -- j) { if (f[x][j] && siz[f[x][j]] <= t) x = f[x][j]; } int fa = f[x][0]; ans[v] += (z[u] - y[u] * siz[v]) - ((z[fa] - y[fa] * siz[v]) << 1) + y[fa] * (S - siz[v]); } } int main() { int ti = read(); while (ti --) { n = read(), rt = (n + 1) >> 1, S = num = tim = tot = 0, dep[rt] = 1; for (int i = 1; i <= n; ++ i) { a[i] = read(), fx[i] = i, S += a[i]; head[i] = b[i] = y[i] = z[i] = c[i] = C[i] = 0; } for (int i = 2, u, v, d; i <= n; ++ i) { u = read(), v = read(), d = read(); addEdge(u, v, d), addEdge(v, u, d); lg[i] = lg[i >> 1] + 1; } dfs(rt, 0), dfs1(rt, 0); std::sort(q + 1, q + tot + 1); std::sort(fx + 1, fx + n + 1, [] (int a, int b) { return siz[a] < siz[b]; }); int t = 1; for (int i = 1; i <= tot; ++ i) { while (t <= n && siz[fx[t]] <= (q[i].k >> 1)) { fenwick::modify(c, dfn[fx[t]], 1ll * b[fx[t]] * siz[fx[t]]); ++ t; } q[i].s = fenwick::query(c, q[i].l, q[i].r); } t = n; for (int i = 1; i <= n; ++ i) c[i] = 0; for (int i = tot; i; -- i) { while (t && siz[fx[t]] > (q[i].k >> 1)) { fenwick::modify(c, dfn[fx[t]], 1ll * b[fx[t]] * siz[fx[t]]); fenwick::modify(C, dfn[fx[t]], 1ll * b[fx[t]]); -- t; } q[i].s += fenwick::query(C, q[i].l, q[i].r) * q[i].k - fenwick::query(c, q[i].l, q[i].r); } std::sort(q + 1, q + tot + 1, [] (ask a, ask b) { return a.d < b.d; }); LL res = inf; for (int i = 1; i <= n; ++ i) { ans[i] += q[id[i]].s + q[id[i] + 1].s + q[id[i] + 2].s; if (i != rt && ans[i] < res) res = ans[i]; } printf("%lld\n", res); for (int i = 1; i <= n; ++ i) for (int j = 0; 1 << j < dep[i]; ++ j) f[i][j] = 0; } return 0; }