#C241109A. 三人掌

标签（Label）

树上差分
圆方树
LCA
乘法逆元

网址（Website）

题目详情 - 三人掌 - Super

题解 - 三人掌 - Super

题目（Problem）

样例

输入数据 1

输出数据 1

0
1
1

【样例2～6】

见下发文件 chtholly/chtholly2～6.in 和 chtholly/chtholly2～6.ans。

题解（Solution）

$\qquad$还是很好处理的，就推一下式子就可以解决这个问题，主要就是代码的实现。

$\qquad$我当时把 每条边最多属于一个简单环 读成了 每个点最多属于一个简单环 ，后面手跑了 $20$ 个点的大样例才发现自己读错了。。。

$\qquad$原来这个代码有 $\mathrm{5k}$ ，删删减减就只有 $3k$ 了。

$\qquad$想来，其实我的那种方法也可以作为一道题，而且应该是这道题的弱化版，但是对于这个弱化版，如果没有想到圆方树，码量和枚举情况就会急剧增加，反而难以处理。。那我还得庆幸自己遇到了更难的题目，让我可以想出更简单的打法。

出题者题解

算法分析

测试点 $1 \sim 4$ (20pts)

每次询问时暴力搜索所有路径，找到所有满足条件的路径即可。

测试点 $5 \sim 10$ (30pts)

可以将最短路径取出，再对最短路上的边进行背包，决策每一条边是否绕到另一个点使距离增加 $1$。

测试点 $11 \sim 14$ (20pts)

任意两点之间只有一条简单路径，求出其长度判断是否等于 $k$ 即可。

测试点 $15 \sim 20$ (30pts)

如题目名称所示，原图是一个仙人掌，且满足简单环长度均为 $3$。

考虑分析两点之间的最短路径，可以发现若这条路径上存在一条边被包含在一个三元环中，那么就可以通过绕行的方式使这条路径的长度增加 $1$。对于一组询问 $(x,y,k)$，令 $x \rightarrow y$ 的最短路径长为 $len$，共有 $p$ 条最短路径上的边在三元环中，则答案为 $\binom{p}{k-len}$。

可以使用 tarjan 算法找到所有三元环，再建出圆方树后分别计算最短路径长度和三元环个数即可。时间复杂度 $O(n \log n)$。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#include<stack>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int N = 1012345;
const int B = 17;
bool ST;
int bas[N],inv[N];
int tid,Tt;
inline void mul(int &x,int y){x=x*y%mod;}
inline int ksm(int x,int k){
	int res=1;while(k){
		if(k&1) mul(res,x);
		mul(x,x),k>>=1;
	}return res;
}inline int C(int n,int m){
	if(n==m || n==0 || m==0) return 1;
	return bas[n]*inv[m]%mod*inv[n-m]%mod;
}

int n,m,q;

vector<int> e[N],ft[N];

int dfn[N],low[N],t;
int siz[N],cnt;
stack<int> st;
void tarjan(int x,int fa){
	dfn[x]=low[x]=++t, st.emplace(x);
	for(auto y:e[x]){
		if(y==fa) continue;//无向图不能连向父亲 
		if(!dfn[y]){
			tarjan(y,x),low[x]=min(low[x],low[y]);
			if(dfn[x]<=low[y]){
				cnt++;
				ft[x].emplace_back(cnt);
				siz[cnt]++;
				while(st.top()!=y){
					ft[cnt].emplace_back(st.top());
					siz[cnt]++;
					st.pop();
				}
				ft[cnt].emplace_back(y);
				siz[cnt]++;
				st.pop();
			}
		}else low[x] = min(low[x], dfn[y]);
	}
}

struct LCA{
	int f[N][24], dfn[N], idx;
	int dep[N], val[N], d[N];
	void dfs(int x,int F){
		f[dfn[x]=++idx][0] = F, dep[x]=dep[F]+1,
		d[x]=d[F]+(F>n), val[x]=val[F]+(siz[F]==3);
		for(auto y:ft[x]) if(y^F) dfs(y,x);
	}
	inline int cmn(int x,int y){return dfn[x]<dfn[y]?x:y;}
	inline int lca(int x,int y){
		if(x==y) return x;
		if((x=dfn[x])>(y=dfn[y])) swap(x,y);
		int d = __lg(y-x++);
		return cmn(f[x][d], f[y-(1<<d)+1][d]);
	}
	void init(){
		dfs(1,0);
		For(j,1,18) for(int i=1;i+(1<<j)-1<=cnt;i++)
			f[i][j] = cmn(f[i][j-1], f[i+(1<<(j-1))][j-1]);
	}
	inline int dis(int x,int y){return dep[x]+dep[y]-(dep[lca(x,y)]<<1);}
	inline int calc_huan(int x,int y){
		int F = lca(x,y);return val[x]+val[y]-(val[F]<<1)-(siz[F]==3);}
	inline int calc_fang(int x,int y){
		int F = lca(x,y);return d[x]+d[y]-(d[F]<<1)-(siz[F]==3);}
}G;

void Solve(){
	n=rd(),m=rd(),q=rd(),cnt=n;
	For(i,1,m){
		int x=rd(),y=rd();
		e[x].emplace_back(y);
		e[y].emplace_back(x);
	}tarjan(1,0);
	G.init();
	while(q--){
		int x=rd(),y=rd(),k=rd();
		int dis = G.dis(x,y);
		int tmp = G.calc_fang(x,y);
		int huan = G.calc_huan(x,y);
		k -= dis-tmp;
		if(k<0 || k>huan) printf("0\n");
		else printf("%lld\n",C(huan, k));
	}
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("chtholly.in","r",stdin);
	freopen("chtholly.out","w",stdout);
	bas[0]=1;For(i,1,N-5) bas[i]=bas[i-1]*i%mod;
	inv[N-5] = ksm(bas[N-5],mod-2);
	Rof(i,N-6,1) inv[i] = inv[i+1]*(i+1)%mod;
	tid=rd(),Tt=1;double Tim=clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}