[UOJ207]共价大爷游长沙 题解
题目地址:UOJ:共价大爷游长沙 – 题目 – Universal …
May all the beauty be blessed.
题目地址:CodeChef:Chef and Graph Queries | CodeChef
大厨有一个无向图G。顶点从1到N标号,边从1到M标号。
大厨有Q对询问Li,Ri(1≤Li≤Ri≤M)。对于每对询问,大厨想知道当仅保留编号X满足Li≤X≤Ri所在的边时,图G中有多少连通块。
请帮助大厨回答这些询问。
输入格式:
输入数据的第一行包含一个整数T,表示数据组数。对于每组数据,第一行包含三个整数N,M,Q。接下来的M行,每行包含两个整数Vi,Ui,依次表示一条无向边。接下来的Q行,每行包含两个整数Li,Ri,依次表示一组询问。
输出格式:
对于每组询问,输出对应的连通块数。
输入样例#1:
2 3 5 4 1 3 1 2 2 1 3 2 2 2 2 3 1 5 5 5 1 2 1 1 1 1 1 1 1
输出样例#1:
2 1 3 1 1
我们考虑一条边会对连通块产生什么影响,加一条边会合并某两个连通块,使得答案减少1,当然这仅当加这条边不会成环以及没有重边和自环的时候才会产生影响。因此我们考虑维护一个生成树,使得每加一条边,如果成环,删去该环中编号最小的边。该生成树上编号为[Li, Ri]的边有多少条,答案就是n-几。我们可以在逐条加边的过程中动态维护生成树以及生成树上的边编号计数。动态维护生成树可以用LCT做,而边编号计数则使用权值线段树。
这道题目的强制在线升级版可以看[BZOJ3514]Codechef MARCH14 GERALD07加强版 题解 | KSkun’s Blog。
LCT和线段树都是常数大的东西,还好跑过了。
// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>
#include <algorithm>
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int readint() {
register int res = 0, neg = 1;
char c = fgc();
while(c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 400005, INF = 1e9;
struct LCTNode {
int ch[2], fa, val, mn;
bool rev;
} lct[MAXN];
inline bool isleft(int p) {
return lct[lct[p].fa].ch[0] == p;
}
inline bool isroot(int p) {
register int fa = lct[p].fa;
return lct[fa].ch[0] != p && lct[fa].ch[1] != p;
}
inline void update(int p) {
register int ls = lct[p].ch[0], rs = lct[p].ch[1];
lct[p].mn = p;
if(lct[lct[ls].mn].val < lct[lct[p].mn].val) lct[p].mn = lct[ls].mn;
if(lct[lct[rs].mn].val < lct[lct[p].mn].val) lct[p].mn = lct[rs].mn;
}
inline void reverse(int p) {
std::swap(lct[p].ch[0], lct[p].ch[1]);
lct[p].rev ^= 1;
}
inline void pushdown(int p) {
register int ls = lct[p].ch[0], rs = lct[p].ch[1];
if(lct[p].rev) {
if(ls) reverse(ls);
if(rs) reverse(rs);
lct[p].rev ^= 1;
}
}
int sta[MAXN], stop;
inline void pushto(int p) {
stop = 0;
while(!isroot(p)) {
sta[stop++] = p;
p = lct[p].fa;
}
pushdown(p);
while(stop) {
pushdown(sta[--stop]);
}
}
inline void rotate(int p) {
register bool t = !isleft(p); register int fa = lct[p].fa, ffa = lct[fa].fa;
lct[p].fa = ffa; if(!isroot(fa)) lct[ffa].ch[!isleft(fa)] = p;
lct[fa].ch[t] = lct[p].ch[!t]; lct[lct[fa].ch[t]].fa = fa;
lct[p].ch[!t] = fa; lct[fa].fa = p;
update(fa);
}
inline void splay(int p) {
pushto(p);
for(register int fa = lct[p].fa; !isroot(p); rotate(p), fa = lct[p].fa) {
if(!isroot(fa)) rotate(isleft(fa) == isleft(p) ? fa : p);
}
update(p);
}
inline void access(int p) {
for(register int q = 0; p; q = p, p = lct[p].fa) {
splay(p);
lct[p].ch[1] = q;
update(p);
}
}
inline void makert(int p) {
access(p);
splay(p);
reverse(p);
}
inline int findrt(int p) {
access(p);
splay(p);
while(lct[p].ch[0]) p = lct[p].ch[0];
return p;
}
inline void split(int u, int v) {
makert(u);
access(v);
splay(v);
}
inline void link(int u, int v) {
split(u, v);
lct[u].fa = v;
}
inline void cut(int u, int v) {
split(u, v);
if(lct[v].ch[0] != u || lct[lct[v].ch[0]].ch[1]) return;
lct[u].fa = lct[v].ch[0] = 0;
}
inline int query(int u, int v) {
split(u, v);
return lct[v].mn;
}
int sgt[MAXN << 2];
inline void insert(int o, int l, int r, int x, int v) {
if(l == r) {
sgt[o] += v;
return;
}
register int mid = (l + r) >> 1;
if(x <= mid) insert(o << 1, l, mid, x, v);
else insert((o << 1) | 1, mid + 1, r, x, v);
sgt[o] = sgt[o << 1] + sgt[(o << 1) | 1];
}
inline int query(int o, int l, int r, int ll, int rr) {
if(l >= ll && r <= rr) return sgt[o];
register int mid = (l + r) >> 1, res = 0;
if(ll <= mid) res += query(o << 1, l, mid, ll, rr);
if(rr > mid) res += query((o << 1) | 1, mid + 1, r, ll, rr);
return res;
}
int T, n, m, q, ut, vt, lst[MAXN], u[MAXN], v[MAXN], ans[MAXN];
struct Edge {
int u, v;
} edge[MAXN];
struct Query {
int l, r, id;
inline bool operator<(const Query &rhs) const {
return r < rhs.r;
}
} quer[MAXN];
int main() {
T = readint();
while(T--) {
n = readint(); m = readint(); q = readint();
// init
for(int i = 0; i <= n + m; i++) {
lct[i].ch[0] = lct[i].ch[1] = lct[i].fa = lct[i].mn = lct[i].rev = 0;
lct[i].val = INF;
}
memset(sgt, 0, sizeof(sgt));
// read
for(int i = 1; i <= m; i++) {
edge[i].u = readint(); edge[i].v = readint();
}
for(int i = 1; i <= q; i++) {
quer[i].l = readint(); quer[i].r = readint(); quer[i].id = i;
}
std::sort(quer + 1, quer + q + 1);
// work
int tot = n, ptr = 1;
for(int i = 1; i <= m; i++) {
int u = edge[i].u, v = edge[i].v;
if(u != v && findrt(u) == findrt(v)) {
int t = query(u, v), tv = lct[t].val;
cut(edge[tv].u, t);
cut(edge[tv].v, t);
insert(1, 1, m, tv, -1);
}
if(u != v) {
tot++;
lct[tot].mn = tot;
lct[tot].val = i;
link(u, tot);
link(v, tot);
insert(1, 1, m, i, 1);
}
while(ptr <= q && quer[ptr].r <= i) {
if(quer[ptr].r == i) {
ans[quer[ptr].id] = n - query(1, 1, m, quer[ptr].l, quer[ptr].r);
}
ptr++;
}
}
for(int i = 1; i <= q; i++) {
printf("%d\n", ans[i]);
}
}
return 0;
}
题目地址:洛谷:【P2634】[国家集训队]聪聪可可 – 洛谷、BZOJ:Problem 2152. — 聪聪可可
聪聪和可可是兄弟俩,他们俩经常为了一些琐事打起来,例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑(可是他们家只有一台电脑)……遇到这种问题,一般情况下石头剪刀布就好了,可是他们已经玩儿腻了这种低智商的游戏。
他们的爸爸快被他们的争吵烦死了,所以他发明了一个新游戏:由爸爸在纸上画n个“点”,并用n-1条“边”把这n个“点”恰好连通(其实这就是一棵树)。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点(当然他们选点时是看不到这棵树的),如果两个点之间所有边上数的和加起来恰好是3的倍数,则判聪聪赢,否则可可赢。
聪聪非常爱思考问题,在每次游戏后都会仔细研究这棵树,希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。
输入格式:
输入的第1行包含1个正整数n。后面n-1行,每行3个整数x、y、w,表示x号点和y号点之间有一条边,上面的数是w。
输出格式:
以即约分数形式输出这个概率(即“a/b”的形式,其中a和b必须互质。如果概率为1,输出“1/1”)。
输入样例#1:
5 1 2 1 1 3 2 1 4 1 2 5 3
输出样例#1:
13/25
直接把距离、边权对3取模存起来,这样可以减少模运算的次数,优化常数。
统计一个子树下点的距离对3取余为0、1、2的点有多少,答案即c_0^2 + 2c_1c_2(距离被3整除的点之间以及和根,距离余3为1、2的点互相构成点对)。然后把不合法方案减掉,套个gcd,就解决了。
// Code by KSkun, 2018/3
#include <cstdio>
inline int max(int a, int b) {
return a > b ? a : b;
}
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int readint() {
register int res = 0, neg = 1;
char c = fgc();
while(c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 20005, INF = 1e9;
int n, m, ut, vt, wt, k, rt, res = 0;
int siz[MAXN], dep[MAXN], msz[MAXN], sum;
bool vis[MAXN];
struct Edge {
int to, w, nxt;
} gra[MAXN << 1];
int head[MAXN], tot = 0;
inline void addedge(int u, int v, int w) {
tot++;
gra[tot].to = v;
gra[tot].w = w;
gra[tot].nxt = head[u];
head[u] = tot;
}
int c[3];
inline void getroot(int u, int fa) {
siz[u] = 1;
msz[u] = 0;
for(int i = head[u]; i; i = gra[i].nxt) {
int v = gra[i].to;
if(vis[v] || v == fa) continue;
getroot(v, u);
siz[u] += siz[v];
msz[u] = max(msz[u], siz[v]);
}
msz[u] = max(msz[u], sum - siz[u]);
if(msz[u] < msz[rt]) rt = u;
}
inline void caldep(int u, int fa) {
c[dep[u]]++;
for(int i = head[u]; i; i = gra[i].nxt) {
int v = gra[i].to, w = gra[i].w;
if(vis[v] || v == fa) continue;
dep[v] = (dep[u] + w) % 3;
caldep(v, u);
}
}
inline int work(int u, int w) {
c[0] = c[1] = c[2] = 0;
dep[u] = w;
caldep(u, 0);
return c[0] * c[0] + c[1] * c[2] * 2;
}
inline void dfs(int u) {
res += work(u, 0);
vis[u] = true;
for(int i = head[u]; i; i = gra[i].nxt) {
int v = gra[i].to, w = gra[i].w;
if(vis[v]) continue;
res -= work(v, w);
rt = 0;
sum = siz[v];
getroot(v, 0);
dfs(rt);
}
}
inline int gcd(int a, int b) {
int t;
while(t = a % b) {
a = b; b = t;
}
return b;
}
int main() {
n = readint();
for(int i = 1; i < n; i++) {
ut = readint(); vt = readint(); wt = readint() % 3;
addedge(ut, vt, wt);
addedge(vt, ut, wt);
}
rt = 0;
msz[0] = INF;
sum = n;
getroot(1, 0);
dfs(rt);
int t1 = n * n, t2 = gcd(res, t1);
printf("%d/%d", res / t2, t1 / t2);
return 0;
}