A层联测7

A. 推个柿子直接高就行

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
const int N = 2E5+10;
struct p_s{
	ll x, y;
}pts[N];
ll n;
ll sx, sy, sqx, sqy;
ll calc(ll x, ll y){
	sx = (sx - x )	 % MOD, sy = (sy - y) % MOD, sqx = (sqx - x * x) % MOD, sqy = (sqy - y * y) % MOD;
	ll res = 0;
	res = (x * x%MOD * (n - 1)%MOD + y * y%MOD * (n - 1)%MOD + sqx + sqy) % MOD;
	res = (res - 2 * x%MOD * sx%MOD - 2 * y % MOD * sy % MOD) % MOD;
	sx = (sx + x) % MOD, sy = (sy + y) % MOD, sqx = (sqx + x * x) % MOD, sqy = (sqy + y * y) % MOD;
	return (res + MOD) % MOD;
}
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++i){
		cin >> pts[i].x >> pts[i].y;
	}
	for(int i = 1; i <= n; ++i){
		sx = (sx + pts[i].x) % MOD;
		sy = (sy + pts[i].y) % MOD;
		sqx = (sqx + pts[i].x * pts[i].x % MOD) % MOD;
		sqy = (sqy + pts[i].y * pts[i].y % MOD) % MOD;
	}
	for(int i = 1; i <= n; ++i){
		cout << calc(pts[i].x, pts[i].y)<<"\n";
	}
	return 0;
}

B.
考场上写的树剖，树剖挂了， 跑出来重链长度全是1，懒得调了。
点分树暴力跳就行。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 10, E = 2 * N, INF = 0x3f3f3f3f;
int col[N];
int n, q;
struct graph{
	struct edge{
		int nxt, to;
	}e[E];
	int elen, head[N];
	void inse(int frm, int to){
		e[++elen] = {head[frm], to};
		head[frm] = elen;
	}
	void insf(int u, int v){
		inse(u, v), inse(v, u);
	}
	int ct, tot, wt[N], siz[N];
	int fat[N], top[N], son[N], dep[N];
	void dfs1(int u){
		siz[u] = 1;
		dep[u] = dep[fat[u]] + 1;
		for(int i = head[u]; i;i = e[i].nxt){
			int v = e[i].to;
			if(v == fat[u]) continue;
			fat[v] = u;
			dfs1(v);
			siz[u] += siz[v];
			if(siz[son[u]] < siz[v]) son[u] = v;
		}
	}
	void dfs2(int u, int tp){
		top[u] = tp;
		if(son[u]) dfs2(son[u], tp);
		for(int i = head[u]; i;i = e[i].nxt){
			int v = e[i].to;
			if(v == fat[u] || v == son[u]) continue;
			dfs2(v, v);
		}
	}
	int glca(int u, int v){
		while(top[u] != top[v]){
			if(dep[top[u]] < dep[top[v]]) swap(u, v);
			u = fat[top[u]];
		}
		if(dep[u] > dep[v]) swap(u, v);
		return u;
	}
	int gdis(int u, int v){
		return dep[u] + dep[v] - 2 * dep[glca(u, v)];
	}
	bool vis[N];
	void getct(int u, int f){
		siz[u] = 1, wt[u] = 0;
		for(int i = head[u]; i; i= e[i].nxt){
			int v = e[i].to;
			if(vis[v] || v == f) continue;
			getct(v, u);
			siz[u] += siz[v];
			wt[u] = max(wt[u], siz[v]);
		}
		wt[u] = max(wt[u], tot - siz[u]);
		if(wt[ct] > wt[u]) ct = u;
	}
	int solvect(int u){
		wt[ct = 0] = INF, tot = siz[u];
		getct(u, -1);
		/*
		for(int i = 1; i <= n; ++i){
			cerr<<wt[i] <<" ";
		}
		cerr<<endl;*/
		getct(ct, - 1);
		return ct;
	}
}G;
struct pdc{
	struct edge{
		int nxt, to;
	}e[E];
	int elen, head[N];
	int fat[N];
	void inse(int frm, int to){
		e[++elen] = {head[frm], to};
		head[frm] = elen;
	}
	void build(int u){
		G.vis[u] = true;
		for(int i = G.head[u]; i; i = G.e[i].nxt){
			int v = G.e[i].to;
			if(G.vis[v]) continue;
			int w = G.solvect(v);
			inse(u, w);
			build(w);
			fat[w] = u;
		}
	}
	set<pii> st[N];
	void make_black(int s){
		int u = s;
		while(u){
			st[u].insert({G.gdis(s, u), s});
			u = fat[u];
		}
	}
	void make_white(int s){
		int u = s;
		while(u){
			st[u].erase({G.gdis(s, u), s});
			u = fat[u];
		}
	}
	int query(int s){
		int u = s;
		int ret = INF;
		while(u){
			if(!st[u].empty()){
				ret = min(ret, G.gdis(st[u].begin()->second, s));
			}
			u = fat[u];
		}
		if(ret == INF) return -1;
		return ret;
	}	
	void prt(){
		for(int u = 1; u <= n; ++u){
			cerr<<"fat" << u <<" = " << fat[u] <<endl;
			for(int i = head[u]; i; i = e[i].nxt){
				int v = e[i].to;
				cerr<<u <<" -> " << v << endl;
			}
		}
	}
}T;
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> q;
	for(int i = 1; i< n; ++i){
		int u, v; cin >> u >> v;
		G.insf(u, v);
	}
	G.dfs1(1);
	G.dfs2(1, 1);
	G.getct(1, 0);
	T.build(1);
	for(int i = 1; i <= q; ++i){
		int opt, u;
		cin >> opt >> u;
		if(opt == 1){
			col[u] ^= 1;
			if(col[u]) T.make_black(u);
			else T.make_white(u);
		}else{
			cout <<T.query(u) <<"\n";
		}
	}
	return 0;
}

C. 乱搞AC了
D.
暴力AC了，但是卡不掉，因为玄学优化之后是3s 能跑2e10的。
常数优化技巧：O2/O3不会主动优化函数（即使是系统库max/min这样的函数），所以循环条件里面带着min/max一定要先算出来！！
注意内存局部性优化和简单循环优化