网站推广打包,桂林模板网站建设,高中生做网站网页,电子商务网站开发实践传送门 题意#xff1a;求树上满足三点之间距离两两相等的三元组个数 n≤1e5n\le 1e5n≤1e5 原题数据是n≤5000n\le5000n≤5000 考虑怎么做f[u][i]f[u][i]f[u][i]表示uuu为根#xff0c;深度为iii的点的个数g[u][i]g[u][i]g[u][i]表示uuu为根#xff0c;满足2点到lcalcalca的… 传送门 题意求树上满足三点之间距离两两相等的三元组个数 n≤1e5n\le 1e5n≤1e5 原题数据是n≤5000n\le5000n≤5000 考虑怎么做f[u][i]f[u][i]f[u][i]表示uuu为根深度为iii的点的个数g[u][i]g[u][i]g[u][i]表示uuu为根满足2点到lcalcalca的距离减去lcalcalca到uuu的距离为iii即dep[x]dep[y]−3∗deplcaidep[x]dep[y]-3*dep_{lca}idep[x]dep[y]−3∗deplcai的点对个数 换句话说就是还差iii个距离满足能凑成333元组的点对个数 则ansg[u][i1]∗f[v][i];ansg[u][i1]*f[v][i];ansg[u][i1]∗f[v][i];ansf[u][i−1]∗g[v][i];ansf[u][i-1]*g[v][i];ansf[u][i−1]∗g[v][i];g[u][i1]f[u][i1]∗f[v][i];g[u][i1]f[u][i1]*f[v][i];g[u][i1]f[u][i1]∗f[v][i];f[u][i1]f[v][i];f[u][i1]f[v][i];f[u][i1]f[v][i];g[u][i−1]g[v][i];g[u][i-1]g[v][i];g[u][i−1]g[v][i]; 这式子很显然吧 发现转移的时候f[u][i1]f[v][i];f[u][i1]f[v][i];f[u][i1]f[v][i];g[u][i−1]g[v][i];g[u][i-1]g[v][i];g[u][i−1]g[v][i]; 既然只和深度有关 就可以愉快的长链剖分了 复杂度O(n)O(n)O(n) 据说可以点分O(nlogn)O(nlogn)O(nlogn)关我p事 #includebits/stdc.h
using namespace std;
const int RLEN122|1;
#define ll long long
inline char gc(){static char ibuf[RLEN],*ob,*ib;(obib)(ob(ibibuf)fread(ibuf,1,RLEN,stdin));return (ibob)?EOF:*ib;
}
inline int read(){char chgc();int res0,f1;while(!isdigit(ch)){if(ch-)f-f;chgc();}while(isdigit(ch))res(res(res2)1)(ch^48),chgc();return res*f;
}
const int N1000005;
ll *f[N],*g[N],*id,tmp[N2],ans;
int n,adj[N],nxt[N1],to[N1],dep[N],son[N],cnt;
inline void addedge(int u,int v){nxt[cnt]adj[u],adj[u]cnt,to[cnt]v;
}
void dfs1(int u,int fa){for(int eadj[u];e;enxt[e]){int vto[e];if(vfa)continue;dfs1(v,u);if(dep[v]dep[son[u]])son[u]v;}dep[u]dep[son[u]]1;
}
void dfs2(int u,int fa){if(son[u]){f[son[u]]f[u]1,g[son[u]]g[u]-1,dfs2(son[u],u);}f[u][0]1;ansg[u][0];for(int eadj[u];e;enxt[e]){int vto[e];if(vfa||vson[u])continue;f[v]id,iddep[v],g[v]iddep[v],iddep[v]*2;dfs2(v,u);for(int idep[v]-1;~i;i--){ansg[u][i1]*f[v][i];if(i)ansf[u][i-1]*g[v][i];g[u][i1]f[u][i1]*f[v][i];f[u][i1]f[v][i];}for(int idep[v]-1;i;i--){g[u][i-1]g[v][i];}}
}
int main(){nread();for(int i1;in;i){int uread(),vread();addedge(u,v),addedge(v,u);}dfs1(1,0);idtmp;f[1]id,iddep[1],g[1]iddep[1],iddep[1]*2;dfs2(1,0);coutans;
}转载于:https://www.cnblogs.com/stargazer-cyk/p/11145583.html
