本文将带您了解关于[BZOJ2179]-大数乘法-FFT模板的新内容，同时我们还将为您解释大数乘法fft的相关知识，另外，我们还将为您提供关于bzoj4827:[Hnoi2017]礼物FFT、bzoj
本文将带您了解关于[BZOJ2179]-大数乘法-FFT模板的新内容，同时我们还将为您解释大数乘法 fft的相关知识，另外，我们还将为您提供关于bzoj 4827: [Hnoi2017] 礼物 FFT、bzoj-1179 (缩点 + 最短路)、BZOJ1369/BZOJ2865 【后缀数组+线段树】、BZOJ2125: 最短路 (圆方树)的实用信息。
本文目录一览：- [BZOJ2179]-大数乘法-FFT模板（大数乘法 fft）
- bzoj 4827: [Hnoi2017] 礼物 FFT
- bzoj-1179 (缩点 + 最短路)
- BZOJ1369/BZOJ2865 【后缀数组+线段树】
- BZOJ2125: 最短路 (圆方树)
![[BZOJ2179]-大数乘法-FFT模板（大数乘法 fft）](http://www.gvkun.com/zb_users/upload/2025/04/6f22cb3c-6400-4b03-b70c-5f02cbe84a0d1743985594217.jpg "[BZOJ2179]-大数乘法-FFT模板（大数乘法 fft）")
[BZOJ2179]-大数乘法-FFT模板（大数乘法 fft）
说在前面
这题输入输出真的有毒…
细节调了me一晚上= =#…
题目
BZOJ2179传送门
题面
给出两个n位10进制整数x和y，你需要计算x*y。数字长度
输入输出格式
输入格式：
第一行一个正整数n。 第二行描述一个位数为n的正整数x。 第三行描述一个位数为n的正整数y
输出格式：
输出一行，即x*y的结果
解法
真
把一个数字
注意读入数字的时候，数组下标小的存低位，下标大的存高位，这样写更方便进位，并且不用判断后缀0
下面是自带大常数的代码
#include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std ; const double PI = 3.1415926535897932384626 ; int N,len,expos[131100],ans[131100] ; char ssa[131100],ssb[131100] ; struct Complex{ double x,y ; Complex(){} ; Complex( double x_,double y_ ): x(x_),y(y_) {} ; } ; typedef Complex cpx ; cpx a[131100],b[131100] ; cpx operator + ( const cpx &A,const cpx &B ){ return cpx( A.x+B.x,A.y+B.y ); } cpx operator - ( const cpx &A,const cpx &B ){ return cpx( A.x-B.x,A.y-B.y ); } cpx operator * ( const cpx &A,const cpx &B ){ return cpx( A.x*B.x - A.y*B.y,A.x*B.y + A.y*B.x ); } cpx operator / ( const cpx &A,const double &p ){ return cpx( A.x/p,A.y/p ) ; } void FFT( cpx *a,int fix ){ for( int i = 1 ; i < N ; i ++ ) if( expos[i] > i ) swap( a[i],a[ expos[i] ] ) ; for( int id = 2 ; id <= N ; id <<= 1 ){ cpx Wid = cpx( cos( 2 * PI * fix / id ),sin( 2 * PI * fix / id ) ) ; for( int j = 0 ; j < N ; j += id ){ cpx W = cpx( 1,0 ) ; for( int k = j ; k < j + id/2 ; k ++ ){ cpx u = a[k],v = a[k+id/2] ; a[k] = u + v * W ; a[k+id/2] = u - v * W ; W = W * Wid ; } } } if( fix == -1 ) for( int i = 0 ; i < N ; i ++ ) a[i] = a[i] / N ; } void solve(){ FFT( a,1 ) ; FFT( b,1 ) ; for( int i = 0 ; i < N ; i ++ ) a[i] = a[i] * b[i] ; FFT( a,-1 ) ; int anslen = 2 * len - 1 ; for( int i = 0 ; i <= 2 * len - 1 ; i ++ ){ ans[i] += a[i].x + 0.5 ; if( ans[i] >= 10 ){ ans[i+1] += ans[i]/10 ; ans[i] %= 10 ; } } for( int i = anslen ; i >= 0 ; i -- ) if( ans[i] != 0 ){ for( int j = i ; j >= 0 ; j -- ) printf( "%d",ans[j] ) ; return ; } } int main(){ scanf( "%d",&len ) ; scanf( "%s%s",ssa,ssb ) ; for( int i = 1 ; ; i <<= 1 ) if( i >= len * 2 ){ N = i ; break ; } for( int i = 0 ; i < len ; i ++ ) a[len-i-1].x = ssa[i] - ''0'',b[len-i-1].x = ssb[i] - ''0'' ; for( int i = 1,aim = 0 ; i < N ; i ++ ){ int tmp = N >> 1 ; while( aim&tmp ) aim ^= tmp,tmp >>= 1 ; aim ^= tmp ; expos[i] = aim ; } solve() ; }
一点理解
FFT优化的不是单项运算，而是一次性把
每次都是把一个多项式拆分成两个多项式的和与差
数组里存的就是这些
![bzoj 4827: [Hnoi2017] 礼物 FFT](http://www.gvkun.com/zb_users/upload/2025/04/413d2a43-3165-4d00-8e13-0c8c9cc197d41743985595061.jpg "bzoj 4827: [Hnoi2017] 礼物 FFT")
bzoj 4827: [Hnoi2017] 礼物 FFT
两个数列的加和移动其实可以看成是一个数列的加减和移动。(想一想，为什么)
我们设第一个数列加的值为 k，
则 $$ \displaystyle \sum {i=1}^{n}(x_i+k-y_i)^2\=\displaystyle \sum{i=1}^n (x_i^2+k^2+y_i^2+2kx_i-2ky_i-2x_iy_i)\=\displaystyle \sum_{i=1}^nx_i^2+\displaystyle \sum_{i=1}^ny_i^2 +nk^2+2kSum_x-2kSum_y-2\displaystyle \sum_{i=1}^nx_iy_i\=\displaystyle \sum_{i=1}^nx_i^2+\displaystyle \sum_{i=1}^ny_i^2 +nk^2+2 (Sum_x-Sum_y) k-2\displaystyle \sum_{i=1}^nx_iy_i $$ 冷静分析.jpg
首先 $\displaystyle \sum_{i=1}^nx_i^2+\displaystyle \sum_{i=1}^ny_i^2$ 还是不会变的，所以我们先加上。
然后 $nk^2+2 (Sum_x-Sum_y) k$ 和怎么移动无关，通过二次函数的知识我们知道 $k\displaystyle =\frac {Sum_x-Sum_y}{n}$ 时最优，注意这时候 k 不一定是整数，需要考虑一下。
最后就是 $2\displaystyle \sum_{i=1}^nx_iy_i$，当然我们希望这个值越大越好，并且这次和 k 无关。到我们发扬人类智慧的时候了，我们将 x 数组反转，然后再复制一倍，我们就惊奇的发现卷积后的数组从 $n+1$ 到 $2n$ 的每一个值就是移动相应个数后的 $2\displaystyle \sum_{i=1}^nx_iy_i$，取个 max 就好啦。
三个加起来就是我们要的答案啦。
时间复杂度 O (n log n).
#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;
int n, m;
LL ans, suma, sumb, zh_AK = -1e18, k = 1e18;
const int N = 400010, mod = 998244353, G = 3, Ginv = (mod + 1) / 3;
int r[N];
LL a[N], b[N];
inline int read()
{
int res = 0; char ch = getchar(); bool XX = false;
for (; !isdigit(ch); ch = getchar())(ch == ''-'') && (XX = true);
for (; isdigit(ch); ch = getchar())res = (res << 3) + (res << 1) + (ch ^ 48);
return XX ? -res : res;
}
LL ksm(LL a, LL b, LL mod)
{
LL res = 1;
for (; b; b >>= 1, a = a * a % mod)
if (b & 1)res = res * a % mod;
return res;
}
void NTT(LL *A, int lim, int opt)
{
for (int i = 0; i < lim; ++i)
r[i] = (r[i >> 1] >> 1) | ((i & 1) ? (lim >> 1) : 0);
for (int i = 0; i < lim; ++i)
if (i < r[i])swap(A[i], A[r[i]]);
int len;
LL wn, w, x, y;
for (int mid = 1; mid < lim; mid <<= 1)
{
len = mid << 1;
wn = ksm(opt == 1 ? G : Ginv, (mod - 1) / len, mod);
for (int j = 0; j < lim; j += len)
{
w = 1;
for (int k = j; k < j + mid; ++k, w = w * wn % mod)
{
x = A[k]; y = A[k + mid] * w % mod;
A[k] = (x + y) % mod;
A[k + mid] = (x - y + mod) % mod;
}
}
}
if (opt == 1)return;
int ni = ksm(lim, mod - 2, mod);
for (int i = 0; i < lim; ++i)A[i] = A[i] * ni % mod;
}
void MUL(LL *A, int n, LL *B, int m)
{
int lim = 1;
while (lim <= (n + m))lim <<= 1;
NTT(A, lim, 1); NTT(B, lim, 1);
for (int i = 0; i < lim; ++i)A[i] = A[i] * B[i] % mod;
NTT(A, lim, -1);
}
signed main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i)a[i] = read(), suma += a[i];
for (int i = 1; i <= n; ++i)b[i] = read(), sumb += b[i];
for (int i = 1; i <= n; ++i)ans += a[i] * a[i] + b[i] * b[i];
for (int i = -201; i <= 201; ++i)k = min(k, n * i * i + 2 * (suma - sumb) * i);
ans += k;
for (int i = 1; i <= n / 2; ++i)swap(a[i], a[n - i + 1]);
for (int i = n + 1; i <= n + n; ++i)a[i] = a[i - n];
MUL(a, n + n, b, n);
for (int i = n + 1; i <= n + n; ++i)zh_AK = max(zh_AK, a[i]);
cout << ans - 2 * zh_AK;
return 0;
}
bzoj-1179 (缩点 + 最短路)
题意：中文题面
解题思路：因为他能重复走且边权都正的，那么肯定一个环的是必须走完的，所以先缩点，在重新建一个图跑最长路
代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int inf=0x7f7f7f7f;
const int maxn=500500;
struct node
{
int num;
int dist;
node(int _num,int _dist):num(_num),dist(_dist){}
friend bool operator<(node a,node b)
{
return a.dist<b.dist;
}
};
struct Edge
{
int next;
int to;
int w;
}edge[maxn],EDGE[maxn];
int low[maxn];
int dfn[maxn];
int scc_cnt;
int cnt,indexx,step,CNT;
int instack[maxn];
int sccno[maxn];
int visit[maxn];
int head[maxn],HEAD[maxn];
int w[maxn];
int val[maxn];
int dist[maxn];
int flag[maxn];
int x[maxn],y[maxn];
int tx,ty;
int n,m;
int cot,start;
int ans;
vector<int>scc[maxn];
void add(int u,int v)
{
edge[cnt].next=head[u];
edge[cnt].to=v;head[u]=cnt++;
}
void add2(int u,int v,int w)
{
EDGE[CNT].next=HEAD[u];EDGE[CNT].to=v;
EDGE[CNT].w=w;HEAD[u]=CNT++;
}
void tarjan(int u)
{
low[u]=dfn[u]=++step;
instack[++indexx]=u;
visit[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(visit[v])
{
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u])
{
scc_cnt++;
scc[scc_cnt].clear();
do
{
scc[scc_cnt].push_back(instack[indexx]);
sccno[instack[indexx]]=scc_cnt;
visit[instack[indexx]]=0;
indexx--;
}
while(u!=instack[indexx+1]);
}
return;
}
void dij(int u)
{
fill(dist+1,dist+1+scc_cnt,-1);
dist[u]=0;
priority_queue<node>que;
que.push(node(u,dist[u]));
while(!que.empty())
{
node z=que.top();que.pop();
int now=z.num;
for(int i=HEAD[now];i!=-1;i=EDGE[i].next)
{
int v=EDGE[i].to;
if(dist[v]<dist[now]+EDGE[i].w)
{
dist[v]=dist[now]+EDGE[i].w;//cout<<dist[v]<<endl;
que.push(node(v,dist[v]));
}
}
}
}
void init()
{
memset(head,-1,sizeof(head));cnt=scc_cnt=indexx=step=0;
memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));
memset(visit,0,sizeof(visit));memset(HEAD,-1,sizeof(HEAD));CNT=0;
}
int main()
{
int n,m;
init();
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&tx,&ty);
x[i]=tx;y[i]=ty;
add(tx,ty);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);
for(int i=1;i<=n;i++)
scanf("%d",&val[i]);
scanf("%d%d",&start,&cot);
for(int i=1;i<=cot;i++)
scanf("%d",&flag[i]);
for(int i=1;i<=scc_cnt;i++)
{
for(int j=0;j<scc[i].size();j++)
{
w[i]+=val[scc[i][j]];
if(scc[i][j]==start)
start=i;
}
}
add2(0,start,w[start]);
for(int i=1;i<=m;i++)
{
if(sccno[x[i]]==sccno[y[i]])
continue;
else
{
add2(sccno[x[i]],sccno[y[i]],w[sccno[y[i]]]);
}
}
dij(0);
ans=0;
for(int i=1;i<=cot;i++)
{
ans=max(ans,dist[sccno[flag[i]]]);
}
printf("%d\n",ans);
}
BZOJ1369/BZOJ2865 【后缀数组+线段树】
Description
XX在进行字符串研究的时候，遇到了一个十分棘手的问题。
在这个问题中，给定一个字符串S，与一个整数K，定义S的子串T=S(i, j)是关于第K位的识别子串，满足以下两个条件：
1、i≤K≤j。
2、子串T只在S中出现过一次。
例如，S="banana"，K=5，则关于第K位的识别子串有"nana"，"anan"，"anana"，"nan"，"banan"和"banana"。
现在，给定S，XX希望知道对于S的每一位，最短的识别子串长度是多少，请你来帮助他。
Input
仅一行，输入长度为N的字符串S。
Output
输出N行，每行一个整数，第i行的整数表示对于第i位的最短识别子串长度。
Sample Input
agoodcookcooksgoodfood
Sample Output
1 2 3 3 2 2 3 3 2 2 3 3 2 1 2 3 3 2 1 2 3 4
HINT
N<=5*10^5
首先发现可以按照每个后缀统计贡献
然后直接把每个后缀和前后排名的串lcp的max:len求出来，这些值是不能更新的
然后对于$[i,i+len] $用len+1更新，对于$[i+len,n]$用一个等差数列更新min
等差数列维护直接标记永久化就可以了
然后注意特判是不是没有合法的解
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
const int N = 5e5 + 10;
const int INF_of_int = 1e9;
int typ1[N << 2], typ2[N << 2];
#define LD (t << 1)
#define RD (t << 1 | 1)
void build(int t, int l, int r) {
typ1[t] = INF_of_int;
typ2[t] = -INF_of_int;
if (l == r) return;
int mid = (l + r) >> 1;
build(LD, l, mid);
build(RD, mid + 1, r);
}
void modify(int t, int l, int r, int ql, int qr, int typ, int val) {
if (ql > qr) return;
if (ql <= l && r <= qr) {
if (typ == 1) {
typ1[t] = min(typ1[t], val);
} else {
typ2[t] = max(typ2[t], val);
}
return;
}
int mid = (l + r) >> 1;
if (qr <= mid) modify(LD, l, mid, ql, qr, typ, val);
else if (ql > mid) modify(RD, mid + 1, r, ql, qr, typ, val);
else {
modify(LD, l, mid, ql, mid, typ, val);
modify(RD, mid + 1, r, mid + 1, qr, typ, val);
}
}
void output(int t, int l, int r, int val, int pos) {
if (typ1[t]) val = min(val, typ1[t]);
if (typ2[t]) val = min(val, pos - typ2[t] + 1);
if (l == r) {
printf("%d\n", val);
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) output(LD, l, mid, val, pos);
else output(RD, mid + 1, r, val, pos);
}
struct Suffix_Array {
int s[N], n, m;
int c[N], x[N], y[N];
int sa[N], rank[N], height[N];
void init(int len, char *c) {
n = len, m = 0;
for (int i = 1; i <= n; i++) {
s[i] = c[i];
m = max(m, s[i]);
}
}
void radix_sort() {
for (int i = 1; i <= m; i++) c[i] = 0;
for (int i = 1; i <= n; i++) c[x[y[i]]]++;
for (int i = 1; i <= m; i++) c[i] += c[i - 1];
for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i];
}
void buildsa() {
for (int i = 1; i <= n; i++) x[i] = s[i], y[i] = i;
radix_sort();
int now;
for (int k = 1; k <= n; k <<= 1) {
now = 0;
for (int i = n - k + 1; i <= n; i++) y[++now] = i;
for (int i = 1; i <= n; i++) if (sa[i] > k) y[++now] = sa[i] - k;
radix_sort();
y[sa[1]] = now = 1;
for (int i = 2; i <= n; i++) y[sa[i]] = (x[sa[i]] == x[sa[i - 1]] && x[sa[i] + k] == x[sa[i - 1] + k]) ? now : ++now;
swap(x, y);
if (now == n) break;
m = now;
}
}
void buildrank() {
for (int i = 1; i <= n; i++) rank[sa[i]] = i;
}
void buildheight() {
for (int i = 1; i <= n; i++) {
int k = max(height[rank[i - 1]] - 1, 0);
for (; s[i + k] == s[sa[rank[i] - 1] + k]; k++);
height[rank[i]] = k;
}
}
void build(int len, char *c) {
init(len, c);
buildsa();
buildrank();
buildheight();
}
void solve() {
for (int i = 1; i <= n; i++) {
int len = max(height[rank[i]], height[rank[i] + 1]);
if (i + len > n) continue;
modify(1, 1, n, i, i + len, 1, len + 1);
modify(1, 1, n, i + len, n, 2, i);
}
}
} Sa;
int len;
char s[N];
int main() {
#ifdef dream_maker
freopen("input.txt", "r", stdin);
#endif
scanf("%s", s + 1);
len = strlen(s + 1);
Sa.build(len, s);
build(1, 1, len);
Sa.solve();
for (int i = 1; i <= len; i++) output(1, 1, len, len, i);
return 0;
}
BZOJ2125: 最短路 (圆方树)
Time Limit: 1 Sec Memory Limit: 259 MBSubmit: 1574 Solved: 651
[Submit][Status][Discuss]
Description
给一个 N 个点 M 条边的连通无向图，满足每条边最多属于一个环，有 Q 组询问，每次询问两点之间的最短路径。
Input
输入的第一行包含三个整数，分别表示 N 和 M 和 Q 下接 M 行，每行三个整数 v，u，w 表示一条无向边 v-u，长度为 w 最后 Q 行，每行两个整数 v，u 表示一组询问
Output
输出 Q 行，每行一个整数表示询问的答案
Sample Input
9 10 2
1 2 1
1 4 1
3 4 1
2 3 1
3 7 1
7 8 2
7 9 2
1 5 3
1 6 4
5 6 1
1 9
5 7
1 2 1
1 4 1
3 4 1
2 3 1
3 7 1
7 8 2
7 9 2
1 5 3
1 6 4
5 6 1
1 9
5 7
Sample Output
5
6
6
HINT
对于 100% 的数据，N<=10000，Q<=10000
Source
圆方树好毒瘤神奇啊 qwq。
对于这题来说的话，首先把圆方树弄出来
考虑询问的两个点，如果他们的 lca 是圆点，那么直接树上前缀和相加
如果不是圆点，那么他们的 lca 一定是在一个环内，
我们可以维护出环内任意一点到环的根节点（也就是 $dfn$ 最小的节点）的最短路径
然后分类讨论一下即可
对于一个点如何跳的它 lca 所在的环上，这里有个骚操作。
我们考虑树链剖分的过程
如果这个节点是重儿子，因为重儿子的 dfs 序是与父节点连续的，所以要求的点就是 lca 的 dfs 中对应的下一个节点
如果不是重儿子，那么我们一直跳，直到跳到 lca 处位置，那么要求的点就是来时离 lca 最近的那个节点
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int MAXN = 1e6 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < ''0'' || c > ''9'') {if(c == ''-'') f = -1; c = getchar();}
while(c >= ''0'' && c <= ''9'') x = x * 10 + c - ''0'', c = getchar();
return x * f;
}
int N, M, Q;
struct Edge {
int u, v, w, nxt;
}E[MAXN];
int head[MAXN], num = 1;
inline void AddEdge(int x, int y, int z) {
E[num] = (Edge){x, y, z, head[x]};
head[x] = num++;
}
vector<Edge> vec[MAXN];
inline void add_edge(int x, int y, int z) {
vec[x].push_back((Edge){x, y, z});
vec[y].push_back((Edge){y, x, z});
}
int low[MAXN], dfn[MAXN], times, fa[MAXN], cdis[MAXN], dis[MAXN], tot;
inline void Build(int x, int y, int w) {
for(int i = y; i != x; i = fa[i]) cdis[i] = w, w += dis[i];
cdis[++tot] = w; add_edge(tot, x, 0);//建方点
for(int i = y; i != x; i = fa[i]) add_edge(tot, i, min(cdis[i], w - cdis[i]));
}
void Tarjan(int x, int _fa) {
dfn[x] = low[x] = ++times; fa[x] = _fa;
for(int v, i = head[x]; i != -1; i = E[i].nxt) {
if((v = E[i].v) == _fa) continue;
if(!dfn[v]) dis[v] = E[i].w, Tarjan(v, x), low[x] = min(low[x], low[v]);
else low[x] = min(low[x], dfn[v]);
if(low[v] > dfn[x]) add_edge(x, v, E[i].w);
}
// can I take this into for ?
for(int v, i = head[x]; i != -1; i = E[i].nxt)
if(fa[(v = E[i].v)] != x && dfn[v] > dfn[x])//如果不是负边，那么一定出现了环
Build(x, v, E[i].w);
}
int siz[MAXN], son[MAXN], top[MAXN], deep[MAXN], Index = 0, point[MAXN];
void dfs1(int x, int _fa) {
fa[x] = _fa; siz[x] = 1;
for(int i = 0, v; i < vec[x].size(); i++) {
if((v = vec[x][i].v) == _fa) continue;
dis[v] = dis[x] + vec[x][i].w;
deep[v] = deep[x] + 1;
dfs1(v, x);
siz[x] += siz[v];
if(siz[v] > siz[son[x]]) son[x] = v;
}
}
void dfs2(int x, int topf) {
top[x] = topf; point[dfn[x] = ++Index] = x;
if(!son[x]) return ;
dfs2(son[x], topf);
for(int i = 0, v; i < vec[x].size(); i++)
if(!top[v = vec[x][i].v])
dfs2(v, v);
}
int LCA(int x, int y) {
while(top[x] != top[y]) {
if(deep[top[x]] < deep[top[y]]) swap(x, y);
x = fa[top[x]];
}
if(deep[x] < deep[y]) swap(x, y);
return y;
}
int Jump(int x, int lca) {
int las;
while(top[x] != top[lca]) las = top[x], x = fa[top[x]];//las = top[x] not x
return x == lca ? las : point[dfn[lca] + 1];//这里要写lca
}
int abs(int x) {
return x < 0 ? -x : x;
}
int main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
#endif
tot = N = read(); M = read(); Q = read();
memset(head, -1, sizeof(head));
for(int i = 1; i <= M; i++) {
int x = read(), y = read(), z = read();
AddEdge(x, y, z); AddEdge(y, x, z);
}
Tarjan(1, 0); dis[1] = 0; deep[1] = 1;
//for(int i = 1; i <= N; i++) printf("%d ", dfn[i]); puts("");
//for(int i = 1; i <= N; i++) printf("%d ", vec[i].size()); puts("");
//printf("%d\n", tot);
dfs1(1, 0);
dfs2(1, 1);
//for(int i = 1; i <= tot; i++) printf("%d ", top[i]); puts("");
while(Q--) {
int x = read(), y = read();
int lca = LCA(x, y);
if(lca <= N) {printf("%d\n", dis[x] + dis[y] - (dis[lca] << 1)); continue;}
int p1 = Jump(x, lca);
int p2 = Jump(y, lca);
int ans = dis[x] - dis[p1] + dis[y] - dis[p2] + min(abs(cdis[p2] - cdis[p1]),
cdis[lca] - abs(cdis[p2] - cdis[p1]));
printf("%d\n", ans);
}
return 0;
}
今天关于[BZOJ2179]-大数乘法-FFT模板和大数乘法 fft的介绍到此结束，谢谢您的阅读，有关bzoj 4827: [Hnoi2017] 礼物 FFT、bzoj-1179 (缩点 + 最短路)、BZOJ1369/BZOJ2865 【后缀数组+线段树】、BZOJ2125: 最短路 (圆方树)等更多相关知识的信息可以在本站进行查询。
本文标签：
