天津网站开发tjniu,网页制作模板dw,短网址还原工具,直装模板源码正题
题目链接:https://www.luogu.com.cn/problem/P4103 题目大意 nnn个点的一棵树#xff0c;mmm次给出一些点#xff0c;求最近点对#xff0c;最远点对和所有点对的距离和。 解题思路
先构造一棵虚树#xff0c;然后在上面dpdpdp统计答案即可。 codecodecode
#includ…正题
题目链接:https://www.luogu.com.cn/problem/P4103 题目大意
nnn个点的一棵树mmm次给出一些点求最近点对最远点对和所有点对的距离和。 解题思路
先构造一棵虚树然后在上面dpdpdp统计答案即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e610,T20,inf1e18;
struct node{ll to,next;
}a[N*2];
ll n,k,q,tot,st,cnt,ans1,ans2,ans3,dep[N],ls[N];
ll dfn[N],f[N][T1],siz[N],dp[N][2],s[N],p[N];
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(ll x,ll fa){dep[x]dep[fa]1;dfn[x]cnt;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;f[y][0]x;dfs(y,x);}return;
}
ll LCA(ll x,ll y){if(dep[x]dep[y])swap(x,y);for(ll iT;i0;i--)if(dep[f[y][i]]dep[x])yf[y][i];if(xy)return x;for(ll iT;i0;i--)if(f[x][i]!f[y][i])xf[x][i],yf[y][i];return f[x][0];
}
void ins(ll x){if(!st){s[st]x;return;}ll lcaLCA(x,s[st]);while(st1dep[lca]dep[s[st-1]])addl(s[st-1],s[st]),st--;if(dep[lca]dep[s[st]])addl(lca,s[st]),st--;if((!st)||(lca!s[st]))s[st]lca;s[st]x;return;
}
bool cmp(ll x,ll y)
{return dfn[x]dfn[y];}
void solve(ll x){if(siz[x])dp[x][0]dp[x][1]0;else dp[x][0]0,dp[x][1]inf;for(ll ils[x];i;ia[i].next){ll ya[i].to,wdep[y]-dep[x];solve(y);ans3w*siz[y]*(k-siz[y]);if(siz[x]0){ans1max(ans1,dp[x][0]dp[y][0]w);ans2min(ans2,dp[x][1]dp[y][1]w);}dp[x][0]max(dp[x][0],dp[y][0]w);dp[x][1]min(dp[x][1],dp[y][1]w);siz[x]siz[y];siz[y]0;}ls[x]0;return;
}
int main()
{scanf(%lld,n);for(ll i1;in;i){ll x,y;scanf(%lld%lld,x,y);addl(x,y);addl(y,x);} dfs(1,0);for(ll j1;jT;j)for(ll i1;in;i)f[i][j]f[f[i][j-1]][j-1];scanf(%lld,q);memset(ls,0,sizeof(ls));while(q--){scanf(%lld,k);sttot0;for(ll i1;ik;i){scanf(%lld,p[i]);siz[p[i]];}sort(p1,p1k,cmp);if(p[1]!1)s[st]1;for(ll i1;ik;i)ins(p[i]);while(st1)addl(s[st-1],s[st]),st--;ans1ans30;ans2inf;solve(1);siz[1]0;printf(%lld %lld %lld\n,ans3,ans2,ans1);}return 0;
}
