做系统的图标下载网站,火星培训机构收费明细,微信小程序云服务器价格,网站开发网站建设制作费用正题
题目链接:https://www.luogu.com.cn/problem/P7581 题目大意
给出nnn个点的有边权有根树#xff0c;mmm次询问一个节点xxx的所有kkk级儿子两两之间路径长度。 1≤n,m≤1061\leq n,m\leq 10^61≤n,m≤106 解题思路
有根长剖#xff0c;无根点分治。所以这题应该是长剖…正题
题目链接:https://www.luogu.com.cn/problem/P7581 题目大意
给出nnn个点的有边权有根树mmm次询问一个节点xxx的所有kkk级儿子两两之间路径长度。
1≤n,m≤1061\leq n,m\leq 10^61≤n,m≤106 解题思路
有根长剖无根点分治。所以这题应该是长剖先离线一下询问
然后略微分析一下两两的路径长度所以需要合并两棵子树向上的路径合并的时候又需要记录子树的kkk级儿子到该节点的距离和还有kkk级儿子个数。
所以要记录三个东西fi,jf_{i,j}fi,j表示iii节点的jjj级儿子个数gi,jg_{i,j}gi,j表示iii节点的jjj级儿子到根的距离和hi,jh_{i,j}hi,j表示iii节点的jjj级儿子两两之间的路径。
然后这三个用长剖转移就好了。
时间复杂度O(n)O(n)O(n) code
#includecstdio
#includecstring
#includealgorithm
#includevector
#define ll long long
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x-x)
using namespace std;
const ll N1e610,P1e97;
struct node{ll to,next,w;
}a[N1];
ll n,m,tot,p[N],ls[N],ans[N],len[N],son[N],dis[N],F[N],G[N],H[N];
ll *now,*tmp,*buf,*f[N],*g[N],*h[N];
vectorpairll,ll v[N];
void addl(ll x,ll y,ll w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;return;
}
void dfs(ll x,ll fa){for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;dis[y]dis[x]a[i].w;dfs(y,x);if(len[y]len[son[x]])son[x]y;}len[x]len[son[x]]1;return;
}
void solve(ll x,ll fa){f[x][0]1;g[x][0]dis[x];if(son[x]){f[son[x]]f[x]1;g[son[x]]g[x]1;h[son[x]]h[x]1;solve(son[x],x);}for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa||yson[x])continue;f[y]now;nowlen[y];g[y]tmp;tmplen[y];h[y]buf;buflen[y];solve(y,x);for(ll j0;jlen[y];j){ll t1(g[x][j1]-f[x][j1]*dis[x])%P;ll t2(g[y][j]-f[y][j]*dis[x])%P;(h[x][j1]t1*f[y][j]%Pf[x][j1]*t2%P)%P;(h[x][j1]h[y][j])%P;(g[x][j1]g[y][j])%P;f[x][j1]f[y][j];}}for(ll i0;iv[x].size();i){ll kv[x][i].first,idv[x][i].second;if(klen[x])ans[id]0;else ans[id]h[x][k];}return;
}
signed main()
{scanf(%lld%lld,n,m);for(ll i1;in;i){ll x,y,w;scanf(%lld%lld%lld,x,y,w);addl(x,y,w);addl(y,x,w);}for(ll i1;im;i){ll x,k;scanf(%lld%lld,x,k);v[x].push_back(mp(k,i));}dfs(1,1);nowf[1]F;nowlen[1];tmpg[1]G;tmplen[1];bufh[1]H;buflen[1];solve(1,1);for(ll i1;im;i)printf(%lld\n,(ans[i]P)%P);return 0;
}
