LJT的书库题解

原题链接

题目难度较低，看懂题目后特别好想。

注意到题目中说的，一个藏书室最多与两个相同的藏书室相连。那么含有所需书的藏书室是树上的一条链。
但是，书的本数未知，且链的两段可能会继续向下延伸。
具体数量无法确定。

注意到题目是要我们求最小值，那么两个端点是否继续向下连接便不重要了, 而每个藏书库至少会放一本书，所以实际上题目就是要我们求两条路径交集的长度。

task1:

不知道会不会有人写阶乘做法，反正放进去了。

task2: 链

直接用深度计算就好啦。

task3: 菊花图

可以发现，路径重合只会有 \(1, 2, 3\) 三种情况。

所以特判一下 \(a, b, c\) 即可。

task4:

\(n \le 1000, q \le 1000\)。 对于求出两条路径的交集，考虑直接从 \(a\) 和 \(c\) 开始遍历，同时记录数组 \(pre[i]\)。之后，再次遍历两次求出交集大小。

\(25 pts\) 的代码：

#include <bits/stdc++.h>
using namespace std;
#define N 1000010

inline int read(){
    int x = 0, s = 1;
    char c = getchar();
    while(!isdigit(c)){
        if(c == '-')s = -1;
        c = getchar();
    }
    while(isdigit(c)){
        x = x * 10 + (c ^ '0');
        c = getchar();
    }
    return x * s;
}

struct node{
    int v, next;
} t[N << 1];
int f[N];

int bian = 0;
inline void add(int u, int v){
    t[++bian] = (node){v, f[u]}, f[u] = bian;
    t[++bian] = (node){u, f[v]}, f[v] = bian;
    return ;
}

bool vis[N], hav[N];
int ans = 0; 
int pre[N]; 
int fa[N]; 

void dfs1(int now, int father){  // 打上标记  
	pre[now] = father; 
	for(int i = f[now]; i; i = t[i].next){
		int v = t[i].v;
		if(v == father) continue; 
		dfs1(v, now); 
	}
	return ; 
}

void dfs2(int now, int father){
	fa[now] = father;
	for(int i = f[now]; i; i = t[i].next){
		int v = t[i].v;
		if(v != father){
			dfs2(v, now); 
		}
	}
	return ; 
}

int main(){
    int n = read(), T = read(), num = read();
    for(int i = 1;i < n; i++){
        int x = read(), y = read();
        add(x, y);
    }
    while(T--){
    	int a = read(), b = read(), c = read();
		memset(vis, 0, sizeof(vis)); 
		memset(pre, 0, sizeof(hav)); 
		memset(hav, 0, sizeof(hav)); 
		memset(fa, 0, sizeof(fa)); 
		ans = 0; 
		pre[a] = a; 
		dfs1(a, a); 
		int x = b;
		while(x != a && x){
			hav[x] = 1;
			x = pre[x]; 
		}
		hav[a] = 1; 
		dfs2(b, b); 
		x = c;
		while(x != b && x){
			if(hav[x]) ans++;
			x = fa[x]; 
		}
		if(hav[b]) ans++; 
		cout << ans << endl; 
    }
    return 0;
}

满分做法：

\(n \le 1000\) 的做法的弊端在于求交集太慢。其实我们直接求 \(LCA\) 然后用深度计算长度就好啦！

树链剖分模板:
(本来想着卡下倍增常数，怕被骂太毒瘤就算了。)

#include <bits/stdc++.h>
using namespace std;
#define N 1000010

inline int read(){
    int x = 0, s = 1;
    char c = getchar();
    while(!isdigit(c)){
        if(c == '-')s = -1;
        c = getchar();
    }
    while(isdigit(c)){
        x = x * 10 + (c ^ '0');
        c = getchar();
    }
    return x * s;
}

struct node{
    int v, next;
} t[N << 1];
int f[N];

int bian = 0;
inline void add(int u, int v){
    t[++bian] = (node){v, f[u]}, f[u] = bian;
    t[++bian] = (node){u, f[v]}, f[v] = bian;
    return ;
}

int deth[N], siz[N], son[N], fa[N], top[N]; 

#define v t[i].v
void dfs1(int now, int father){
    siz[now] = 1;
    fa[now] = father;
    deth[now] = deth[father] + 1;
    for(int i = f[now]; i; i = t[i].next){
        if(v != father){
            dfs1(v, now);
            siz[now] += siz[v];
            if(siz[v] > siz[son[now]])
                son[now] = v;
        }
    }
    return ;
}

void dfs2(int now, int tp){
    top[now] = tp;
    if(!son[now]) return ;
    dfs2(son[now], tp);
    for(int i = f[now]; i; i = t[i].next){
        if(v != fa[now] && v != son[now])
            dfs2(v, v);
    }
    return ;
}

int lca(int x, int y){
    while(top[x] != top[y]){
        if(deth[top[x]] < deth[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    return deth[x] > deth[y] ? y : x;
} 


#undef v

int main(){
    int n = read(), T = read(), num = read();
    for(int i = 1;i < n; i++){
        int x = read(), y = read();
        add(x, y);
    }
    dfs1(1, 0);
    dfs2(1, 0);
    while(T--){
        int a = read(), b = read(), c = read();
        int ans1 = abs(2 * deth[lca(a, b)] - deth[b] - deth[a]);
        int ans2 = abs(2 * deth[lca(a, c)] - deth[a] - deth[c]);
        int ans3 = abs(2 * deth[lca(b, c)] - deth[b] - deth[c]);
    	printf("%d\n", (ans1  + ans3 - ans2) / 2 + 1);
    }
    return 0;
}