D. Maximum Distributed Tree(DFS)
D. Maximum Distributed Tree(DFS)
思路： d f s dfs dfs讨论一下 m m m与 n ? 1 n-1 n?1的大小关系，然后计算每条边的贡献次数排序即可。
【D. Maximum Distributed Tree(DFS)】没想到最后因为数组开小了一直没 A C AC AC，气死了。
#include
using namespace std;
typedef long long ll;
const int N=1e5+5,M=6e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair
#define fi first
#define se second
#define pb push_back
#define il inline
int n,sz[N],p[N];
vectore[N];
vectorf;
void dfs(int u,int fa){
sz[u]=1;
for(int v:e[u]){
if(v==fa) continue;
dfs(v,u);
sz[u]+=sz[v];
}
ll x=1LL*sz[u]*(n-sz[u]);
f.pb(x);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=1;
i<=n;
i++) e[i].clear(),sz[i]=p[i]=0;
//之前就是因为p[]开的太小，越界了。
f.clear();
for(int i=1;
iq;
for(int i=1;
i<=m;
i++){
scanf("%d",&p[i]);
}
sort(p+1,p+m+1,greater());
int id=1;
int op=0,m1=m;
if(m>n-1){
op=1;
ll x=1;
while(m>=n-1){
x=x*p[id++]%mod;
m--;
}
q.push_back(x);
for(int i=id;
i<=m1;
i++)
q.push_back(1LL*p[i]);
}
dfs(1,0);
sort(f.rbegin(),f.rend());
ll ans=0;
if(op){
for(int i=1;
i 推荐阅读
- 怀念三里屯那家叫做the|怀念三里屯那家叫做the tree 的酒吧
- ztree|ztree 拖拽
- SourceTree|SourceTree 教程文档（了解界面）
- 深度瞎搞|PyTorch单机多卡训练（DDP-DistributedDataParallel的使用）备忘记录
- cs61b week8 -- Binary Search Tree
- webpack总结
- Codeforces|Codeforces Round #263 Div.1 B Appleman and Tree --树形DP【转】
- C++|C++ pbds 库平衡树（tree）
- 机器学习 — Decision Tree
- leetCode解题报告|leetCode解题报告之Binary Tree Level Order Traversal II,I(二叉树层次遍历)