嘉兴网站建设制作,重庆seowhy整站优化,wordpress图片视频分享,品牌建设总结传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a; 思路#xff1a;
简化一下题意就是求树上给定点集中每两个点之间的距离之和#xff0c;相距最远的点#xff0c;相距最近的点。 对于距离和我们统计一下边的贡献就好啦#xff0c;边两头的sizesizesize乘…传送门
文章目录题意思路题意 思路
简化一下题意就是求树上给定点集中每两个点之间的距离之和相距最远的点相距最近的点。 对于距离和我们统计一下边的贡献就好啦边两头的sizesizesize乘起来就好了。对于相距最远的点和相距最近的点我们可以设f[x]f[x]f[x]表示xxx子树中距离xxx最近的关键点的距离g[x]g[x]g[x]表示xxx子树中距离xxx最远的关键点的距离那么f[x]min(f[x],f[v]w[i]),g[x]max(g[x],g[v]w[i])f[x]min(f[x],f[v]w[i]),g[x]max(g[x],g[v]w[i])f[x]min(f[x],f[v]w[i]),g[x]max(g[x],g[v]w[i])当xxx这个点是关键点的时候f[x]0f[x]0f[x]0让后定义ans2,ans3ans2,ans3ans2,ans3分别表示第二第三种答案ans2min(ans2,f[x]f[v]w[i]),ans3max(ans3,g[x]g[v]w[i])ans2min(ans2,f[x]f[v]w[i]),ans3max(ans3,g[x]g[v]w[i])ans2min(ans2,f[x]f[v]w[i]),ans3max(ans3,g[x]g[v]w[i])当然算ans2,ans3ans2,ans3ans2,ans3的时候需要在f,gf,gf,g更新之前算。 但是有一个很大的问题就是我们每次都遍历所有树的话复杂度是O(nq)O(nq)O(nq)的但是∑k≤2∗n\sum k\le2*n∑k≤2∗n所以我们每次都建一颗虚树复杂度就是O(qn)O(qn)O(qn)的了。
不用看dfs2,dfs3dfs2,dfs3dfs2,dfs3写的跟shi一样。
// Problem: P4103 [HEOI2014]大工程
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4103
// Memory Limit: 500 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;// char buf[123],*p1buf,*p2buf;
// #define gc() (p1p2(p2(p1buf)fread(buf,1,121,stdin),p1p2)?EOF:*p1)
// inline bool ig(char c){return c48c57;}
// inline void read(int oi){char c;int f1,res0;while(cgc(),(!ig(c))c^-);c^-?res(c^48):f-1;while(cgc(),ig(c))resres*10(c^48);oif*res;}
// inline void print(int oi){if(oi0)putchar(-),oi~oi1;if(oi9)print(oi/10);putchar(oi%1048);}
// inline void print(LL oi){if(oi0)putchar(-),oi~oi1;if(oi9)print(oi/10);putchar(oi%1048);}
// template class T
bool read(T ret)
{char c;int sgn;T bit0.1;if(cgetchar(), cEOF)return 0;while(c!- c!. (c0 || c9))cgetchar();sgn(c-)? -1:1;ret(c-)? 0:(c-0);while(cgetchar(), c0 c9)retret*10(c-0);if(c || c\n){ret*sgn;return 1;}while(cgetchar(), c0 c9)ret(c-0)*bit, bit/10;ret*sgn;return 1;
}inline void out(LL x)//
{if(x9)out(x/10);putchar(x%100);
}int n,m;
int depth[N],fa[N][20],dfn[N],idx;
int a[N],tot;
int stk[N],top;
int has[N],se[N],dp1[N],dp2[N];
vectorPIIv[N];
LL ans1;
int ans2,ans3;void dfs1(int u,int f) {fa[u][0]f; dfn[u]idx;depth[u]depth[f]1;for(int i1;i18;i) fa[u][i]fa[fa[u][i-1]][i-1];for(auto x:v[u]) {if(x.Xf) continue;dfs1(x.X,u);}
}int lca(int a,int b) {if(depth[a]depth[b]) swap(a,b);for(int i18;i0;i--) if(depth[fa[a][i]]depth[b])afa[a][i];if(ab) return a;for(int i18;i0;i--) if(fa[a][i]!fa[b][i]) afa[a][i],bfa[b][i];return fa[a][0];
}bool cmp(int a,int b) {return dfn[a]dfn[b];
}void insert(int x) {if(!top) stk[top]x;else {int fatherlca(x,stk[top]);while(top1depth[father]depth[stk[top-1]]) {v[stk[top-1]].pb({stk[top],depth[stk[top]]-depth[stk[top-1]]}),top--;}if(depth[father]depth[stk[top]]) v[father].pb({stk[top],depth[stk[top]]-depth[father]}),top--;if(!top||stk[top]!father) stk[top]father;stk[top]x;}
}// void dfs2(int u,int f) {// if(has[u]) se[u]1;// int mx10,mx20;// for(auto x:v[u]) {// if(x.Xf) continue;// dfs2(x.X,u);// se[u]se[x.X];// ans11ll*se[x.X]*(tot-se[x.X])*x.Y;//算边的贡献// int nowdp[x.X]x.Y;// if(nowmx1) mx2mx1,mx1now;// else if(nowmx2) mx2now; // }// //以这个点为两个链的连接点所以这个点是不是关键点不重要// //重要的是有两个链而链的尽头是关键点// if(mx20) ans2max(ans2,1ll*mx1mx2);// else if(has[u]) ans2max(ans2,1ll*mx1mx2);//如果是关键点那么可以以他为链的一端// dp[u]mx1;
// }
//
// void dfs3(int u,int f) {// if(has[u]) {// ff[u]u;// for(auto x:v[u]) {// if(x.Xf) continue;// dfs3(x.X,u);// ans3min(ans3,depth[ff[x.X]]-depth[u]);// }// } else {// int mi1,mi2; mi1mi2INF;// for(auto x:v[u]) {// if(x.Xf) continue;// dfs3(x.X,u);// if(mi1depth[ff[x.X]]) mi2mi1,mi1depth[ff[x.X]],ff[u]ff[x.X];// else if(mi2depth[ff[x.X]]) mi2depth[ff[x.X]];// }// ans3min(ans3,mi2mi1-2*depth[u]);// }
// }
//
void dfs4(int u,int f) {if(has[u]) se[u]1;dp1[u]has[u]? 0:1e9;dp2[u]0;for(auto x:v[u]) {if(x.Xf) continue;dfs4(x.X,u);ans11ll*se[x.X]*(tot-se[x.X])*x.Y;if(se[u]0) {ans2min(ans2,dp1[u]dp1[x.X]x.Y);ans3max(ans3,dp2[u]dp2[x.X]x.Y);}dp1[u]min(dp1[u],dp1[x.X]x.Y);dp2[u]max(dp2[u],dp2[x.X]x.Y);se[u]se[x.X];}
}void clear(int u,int f) {has[u]se[u]dp1[u]dp2[u]0;for(auto x:v[u]) {if(x.Xf) continue;clear(x.X,u);}v[u].clear();
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);//rd_ac();read(n);for(int i1;in-1;i) {int a,b; read(a); read(b);v[a].pb({b,1}); v[b].pb({a,1});}dfs1(1,0);for(int i1;in;i) v[i].clear();read(m);while(m--) {read(tot);for(int i1;itot;i) read(a[i]),has[a[i]]1;sort(a1,a1tot,cmp);top0; ans1ans30; ans2INF;if(a[1]!1) stk[top]1;for(int i1;itot;i) insert(a[i]);while(top1) v[stk[top-1]].pb({stk[top],depth[stk[top]]-depth[stk[top-1]]}),top--;//dfs2(1,0); dfs3(1,0);dfs4(1,0);//printf(%lld %d %d\n,ans1,ans2,ans3);out(ans1); putchar( );out(ans2); putchar( );out(ans3); putchar(\n);clear(1,0);}return 0;
}
/**/
