网站结构优化,重庆新闻联播今天,精准流量推广,wordpress content widgetsProblem - 1746D - Codeforces 思路#xff1a;先分析一下题意#xff0c;根据第一条性质#xff0c;每次只能够从1开始#xff0c;而第二条性质则表明对于每个节点来说#xff0c;经过这个节点的子节点的路径条数应该尽量均衡#xff0c;最大值与最小值相差不能超过1先分析一下题意根据第一条性质每次只能够从1开始而第二条性质则表明对于每个节点来说经过这个节点的子节点的路径条数应该尽量均衡最大值与最小值相差不能超过1所以我们考虑如果当前要选择k个路径而当前节点有cnt个子节点那么每个子节点应该至少经过k/cnt个同时有k%cnt个需要经过k/cnt1个那么我们发现这个问题可以递归的解决那么我们可以考虑用树形dp我们将f[i][0]表示以i为根并且经过ki个f[i][1]表示以i为根并且经过ki1个那么对于叶子节点来说f[i][0]cost[i]*k,f[i][1]cost[i]*(k1)而对于非叶子节点来说因为所有的子节点都至少经过ki个所有我们先将所有子节点的f[j][0]求和为sum令f[i][0]f[i][1]sum那么我们还要再经过k%cnt个那么我们就是挑几个子节点然后让他变为f[j][1]那么我们可以将所有f[j][1]-f[j][0]排个序按照降序排序那么我们只需要将差值加上就相当于这个变为了f[j][1]所以我们只需要求一下前k%cnt的和即可这是对于f[i][0]来说而对于f[i][1]来说则还要多出来一次那么我们只需要求和倒k%cnt1即可并且k%cnt1按照相同的方法取最大的k%cnt1个一定也是正确的因为k%cnt最大为cnt-1个加一为cnt个正好等于子节点的个数所以一定是合法的取法
// Problem: D. Paths on the Tree
// Contest: Codeforces - Codeforces Global Round 23
// URL: https://codeforces.com/problemset/problem/1746/D
// Memory Limit: 256 MB
// Time Limit: 3000 m#includebits/stdc.h
#includesstream
#includecassert
#define fi first
#define se second
#define i128 __int128
using namespace std;
typedef long long ll;
typedef double db;
typedef pairint,int PII;
const double eps1e-7;
const int N5e57 ,M5e57, INF0x3f3f3f3f,mod1e97,mod1998244353;
const long long int llINF0x3f3f3f3f3f3f3f3f;
inline ll read() {ll x0,f1;char cgetchar();while(c0||c9) {if(c-) f-1;cgetchar();}
while(c0c9) {x(ll)x*10c-0;cgetchar();} return x*f;}
inline void write(ll x) {if(x 0) {putchar(-); x -x;}if(x 10) write(x / 10);putchar(x % 10 0);}
inline void write(ll x,char ch) {write(x);putchar(ch);}
void stin() {freopen(in_put.txt,r,stdin);freopen(my_out_put.txt,w,stdout);}
bool cmp0(int a,int b) {return ab;}
templatetypename T T gcd(T a,T b) {return b0?a:gcd(b,a%b);}
templatetypename T T lcm(T a,T b) {return a*b/gcd(a,b);}
void hack() {printf(\n----------------------------------\n);}int T,hackT;
int n,m,k;
int h[N],e[M],ne[M],idx;
ll f[N][2];
int cost[N];void add(int a,int b) {e[idx]b,ne[idx]h[a],h[a]idx;
}void dfs(int u,int k) {f[u][0](ll)cost[u]*k;f[u][1](ll)cost[u]*(k1);int cnt0;for(int ih[u];i!-1;ine[i]) {int je[i];cnt;}if(!cnt) return ;int ak/cnt,bk%cnt;vectorll vis;for(int ih[u];i!-1;ine[i]) {int je[i];dfs(j,a);f[u][0]f[j][0];f[u][1]f[j][0];vis.push_back(f[j][1]-f[j][0]);}sort(vis.begin(),vis.end(),[](ll a,ll b){return ab;});for(int i0;ib;i) f[u][0]vis[i];for(int i0;ib;i) f[u][1]vis[i];
}void solve() {nread(),kread();memset(h,-1,sizeof(int)*(n4));idx0;for(int i2;in;i) {int cread();add(c,i);}for(int i1;in;i) cost[i]read();dfs(1,k);printf(%lld\n,f[1][0]);
} int main() {// init();// stin();// ios::sync_with_stdio(false); scanf(%d,T);// T1; while(T--) hackT,solve();return 0;
}
