F. 异象石
难度适中
考虑增加一个点或减少一个点的时候，对答案产生了哪些贡献
#define PII pair<ll,ll> map<PII, ll> mp; ll n, m, _time = 0; ll head[maxn]; struct node { ll u, v, w; ll next; } e[maxn << 1]; ll dep[maxn];/// save the depth of every node ll fa[maxn][30], lg[maxn], cnt = 0; ll ans; ll dfn[maxn], id[maxn], vis[maxn], dis[maxn]; set<ll> s; void init() { cnt = 0; memset(head, -1, sizeof head); } void add(ll u, ll v, ll w) { e[cnt].v = v; e[cnt].w = w; e[cnt].next = head[u]; head[u] = cnt ++; } void dfs(ll cur, ll rt) { dfn[cur] = ++_time; id[_time] = cur; fa[cur][0] = rt; dep[cur] = dep[rt] + 1; /// the depth of the current node changed dis[cur] = dis[rt] + mp[ {cur, rt}]; for(int i = 1; i <= lg[dep[cur]]; i++) { fa[cur][i] = fa[fa[cur][i - 1]][i - 1]; } for(int i = head[cur]; ~i; i = e[i].next) /// visit all linked nodes { if(e[i].v != rt) dfs(e[i].v, cur); } } void cal() { for(int i = 1; i <= n; i++) { lg[i] = lg[i - 1] + (1LL << lg[i - 1] == i); /// 2 ^ lg[i-1] == i true + 1 } } ll lca(ll x, ll y) { if(dep[x] < dep[y]) swap(x, y); while(dep[x] > dep[y]) x = fa[x][lg[dep[x] - dep[y]] - 1]; if(x == y) return x; for(int k = lg[dep[x]] - 1; k >= 0; k --) { if(fa[x][k] != fa[y][k]) { x = fa[x][k]; y = fa[y][k]; } } return fa[x][0]; } ll getDis(ll u, ll v) { ll _lca = lca(u, v); return dis[u] + dis[v] - 2LL * dis[_lca]; } void update(ll x) { ll y, z; set<ll>::iterator it; x = dfn[x];///time if(!vis[id[x]]) s.insert(x); it = s.lower_bound(x); if(it == s.begin()) y = *--s.end(); else y = *--it; y = id[y]; it = s.upper_bound(x); if(it == s.end()) z = *s.begin(); else z = *it; z = id[z]; if(vis[id[x]]) s.erase(x); x = id[x]; int dis = getDis(x, y) + getDis(x, z) - getDis(y, z); if(!vis[x]) vis[x] = 1, ans += dis; else vis[x] = 0, ans -= dis; } signed main() { cin >> n; cal(); init(); for(int i = 1; i < n; i++) { ll u = read, v = read, w = read; mp[ {u, v}] = w; mp[ {v, u}] = w; add(u, v, w); add(v, u, w); } dfs(1, 0); m = read; ll x; char c; for(int i = 1; i <= m; i++) { cin >> c; if(c == '?') printf("%lld\n", ans >> 1LL); else { scanf("%lld", &x); update(x); } } // cout << ans << endl; return 0; } /** 6 1 2 1 1 3 5 4 1 7 4 5 3 6 4 2 10 + 3 + 1 ? + 6 ? + 5 ? - 6 - 3 ? 5 14 17 10 **/
G. 暗的连锁
难度适中
首先对n-1条边建图，然后对后来的m条边进行处理：
（从度的方面入手）
int u = read, v = read; int _lca = lca(u, v); deg[u] ++; deg[v] ++; deg[_lca] -= 2;
int n, m; int root; int head[maxn]; struct node { int u; int v; int w; int next; } e[maxn]; int dep[maxn];/// save the depth of every node int fa[maxn][30]; int mini[maxn][30]; int lg[maxn]; int cnt = 0; vector<int> son[maxn]; void init() { memset(head, -1, sizeof head); } void add(int u, int v) { e[cnt].u = u; e[cnt].v = v; e[cnt].next = head[u]; head[u] = cnt ++; } void dfs(int cur, int rt) { fa[cur][0] = rt, dep[cur] = dep[rt] + 1; /// the depth of the current node changed for(int i = 1; i <= lg[dep[cur]]; i++) { fa[cur][i] = fa[fa[cur][i - 1]][i - 1]; } for(int i = head[cur]; ~i; i = e[i].next) /// visit all linked nodes { if(e[i].v != rt) dfs(e[i].v, cur), son[cur].push_back(e[i].v); } } void cal() { for(int i = 1; i <= n; i++) { lg[i] = lg[i - 1] + (1 << lg[i - 1] == i); /// 2 ^ lg[i-1] == i true + 1 } } int lca(int x, int y) { if(dep[x] < dep[y]) swap(x, y); while(dep[x] > dep[y]) { x = fa[x][lg[dep[x] - dep[y]] - 1]; } if(x == y) return x; for(int k = lg[dep[x]] - 1; k >= 0; k --) { if(fa[x][k] != fa[y][k]) { x = fa[x][k]; y = fa[y][k]; } } return fa[x][0]; } int deg[maxn]; int ans; void get(int u) { int siz = son[u].size(); for(int i = 0; i < siz; i++) { int to = son[u][i]; get(to); deg[u] += deg[to]; } if(!fa[u][0]) return ; if(deg[u] == 1) ans ++; else if(deg[u] == 0) ans += m; } int main() { cin >> n >> m; cal(); init(); for(int i = 1; i < n; i++) { int u = read, v = read; add(u, v); add(v, u); } dfs(1, 0); for(int i = 1; i <= m; i++) { int u = read, v = read; int _lca = lca(u, v); deg[u] ++; deg[v] ++; deg[_lca] -= 2; } get(1); cout << ans << endl; return 0; } /** 4 1 1 2 2 3 1 4 3 4 3 **/
H. 点的距离
板子题
考虑用深度代替距离即可
#define Clear(x,val) memset(x,val,sizeof x) int n,m; int root; int head[maxn]; struct node { int u; int v; int w; int next; } e[maxn << 1]; int dep[maxn];/// save the depth of every node int fa[maxn][30]; ll dis[maxn]; int lg[maxn]; int cnt = 0; void init() { memset(head,-1,sizeof head); } void add(int u,int v) { e[cnt].u = u; e[cnt].v = v; e[cnt].next = head[u]; head[u] = cnt ++; } void dfs(int cur,int rt) { fa[cur][0] = rt,dep[cur] = dep[rt] + 1;/// the depth of the current node changed for(int i=1; i <= lg[dep[cur]]; i++) { fa[cur][i] = fa[fa[cur][i-1]][i-1]; } for(int i=head[cur]; ~i; i = e[i].next) { /// visit all linked nodes if(e[i].v != rt) dfs(e[i].v,cur); } } void cal() { for(int i=1; i<=n; i++) { lg[i] = lg[i-1] + (1 << lg[i-1] == i);/// 2 ^ lg[i-1] == i true + 1 } } int lca(int x,int y) { if(dep[x] < dep[y]) swap(x,y); while(dep[x] > dep[y]) x = fa[x][lg[dep[x] - dep[y]] - 1]; if(x == y) return y; /// big -> small for(int k = lg[dep[x]] - 1; k >= 0; k --) { if(fa[x][k] != fa[y][k]) { x = fa[x][k]; y = fa[y][k]; } } return fa[x][0]; } int main() { n = read; cal(); init(); for(int i=1; i<n; i++) { int u = read,v = read; add(u,v); add(v,u); } dfs(1,0); m = read; for(int i=1; i<=m; i++) { int x = read,y = read; int _lca = lca(x,y); ll ans = dep[x] + dep[y] - 2 * dep[_lca]; printf("%lld\n",ans); } return 0; } /** 6 1 2 1 3 2 4 2 5 3 6 2 2 6 5 6 **/
l. 晨跑
大水题
求三个数的lcm
int main() { ll a = read, b = read, c = read; ll ans = lcm(lcm(a,b),c); cout << ans <<endl; return 0; }
J. 货物运输
较简单
在维护某节点的2次方级祖先的同时，记录下路径的最小承重，即为答案
int n, m; int root; int head[maxn]; struct node { int u; int v; int w; int next; } e[maxn]; int dep[maxn];/// save the depth of every node int fa[maxn][30]; int mini[maxn][30]; int lg[maxn]; int cnt = 0; void init() { memset(head, -1, sizeof head); } void add(int u, int v, int w) { e[cnt].u = u; e[cnt].v = v; e[cnt].w = w; e[cnt].next = head[u]; head[u] = cnt ++; } void dfs(int cur, int rt, int val) { fa[cur][0] = rt, dep[cur] = dep[rt] + 1; /// the depth of the current node changed mini[cur][0] = val; for(int i = 1; i <= lg[dep[cur]]; i++) { fa[cur][i] = fa[fa[cur][i - 1]][i - 1]; mini[cur][i] = min(mini[cur][i - 1], mini[fa[cur][i - 1]][i - 1]); } for(int i = head[cur]; ~i; i = e[i].next) /// visit all linked nodes { if(e[i].v != rt) dfs(e[i].v, cur, e[i].w); } } void cal() { for(int i = 1; i <= n; i++) { lg[i] = lg[i - 1] + (1 << lg[i - 1] == i); /// 2 ^ lg[i-1] == i true + 1 } } int lca(int x, int y) { int ans = 0x3f3f3f3f; if(dep[x] < dep[y]) swap(x, y); while(dep[x] > dep[y]) { ans = min(ans, mini[x][lg[dep[x] - dep[y]] - 1]); x = fa[x][lg[dep[x] - dep[y]] - 1]; } if(x == y) return ans; /// big -> small for(int k = lg[dep[x]] - 1; k >= 0; k --) { if(fa[x][k] != fa[y][k]) { ans = min(ans, mini[x][k]); ans = min(ans, mini[y][k]); x = fa[x][k]; y = fa[y][k]; } } ans = min(ans, mini[x][0]); ans = min(ans, mini[y][0]); // return fa[x][0]; return ans; } int main() { cin >> n >> m; cal(); init(); for(int i = 1; i < n; i++) { int u = read, v = read, w = read; add(u, v, w); add(v, u, w); } dfs(1, 0, 0x3f3f3f3f); for(int i = 1; i <= m; i++) { int u = read, v = read; int ans = lca(u, v); printf("%d\n", ans); } return 0; } /** 6 5 1 2 2 2 3 5 2 4 2 2 5 3 5 6 1 2 4 6 2 1 3 3 5 1 6 **/
K. 数三角形
组合数学简单题
考虑容斥，减去不符合的情况
需要知道两个整数点之间的整数点的个数 博客第11条
ll cal(ll x){ ll ret = x * (x - 1) * (x - 2); return ret / 6LL; } int n,m; int main() { n = read,m = read; n ++,m ++; ll tot = cal(n * m) - n* cal(m) - m * cal(n); ll sub = 0; // cout << tot <<endl; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ sub += (n - i) * (m - j) * (gcd(i,j) - 1); } } cout << tot - sub * 2 <<endl; return 0; }/// ac_code /** **/
![[LDUoj 倍增] 题解（上）](https://ucc.alicdn.com/pic/developer-ecology/5c21d1fade764277acf711edbc42e21f.png?x-oss-process=image/resize,h_160,m_lfit)