大型o2o网站开发时间,西安哪有做网站的,wordpress小工具缓存,国内漂亮的企业网站解析 它还真的不难。 乐。
这题没做出来有些谔谔。 外层wqs二分显而易见#xff0c;里面不知道为啥我总觉得这个题可以贪心。 然后一直试图在原树直径上下功夫#xff0c;一筹莫展。 看到题解“dp”两个字这题也就做完了… 就相当于要把一棵树分成若干条无交链#xff0c;每…解析 它还真的不难。 乐。
这题没做出来有些谔谔。 外层wqs二分显而易见里面不知道为啥我总觉得这个题可以贪心。 然后一直试图在原树直径上下功夫一筹莫展。 看到题解“dp”两个字这题也就做完了… 就相当于要把一棵树分成若干条无交链每分条需要一定代价最大化价值和。 记录以下每个点向儿子连几条边以及是否和父亲连边之类的即可。 pair用于wqs二分的dp是真香
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
using namespace std;const int N6e5100;
const ll inf3e11;inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}int n,m,k;struct node{int to,nxt,w;
}p[N1];
int fi[N],cnt;
inline void addline(int x,int y,int w){p[cnt](node){y,fi[x],w};fi[x]cnt;
}
#define pr pairll,ll
#define mkp make_pair
pr operator (pr a,pr b){return mkp(a.firstb.first,a.secondb.second);}
pr operator (pr a,ll b){return mkp(a.firstb,a.second);}
pr dp[3][N];
ll w;
void dfs(int x,int fa){dp[0][x]mkp(0,0);dp[1][x]dp[2][x]mkp(-inf,0);for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tofa) continue;dfs(to,x);dp[2][x]max(dp[2][x],max(dp[2][x]dp[0][to],(dp[1][x]dp[1][to])p[i].w));dp[1][x]max(dp[1][x],max(dp[1][x]dp[0][to],(dp[0][x]dp[1][to])p[i].w));dp[0][x]max(dp[0][x],dp[0][x]dp[0][to]);}dp[1][x]max(dp[1][x],dp[0][x]);dp[0][x]max(dp[0][x],mkp(dp[0][x].firstw,dp[0][x].second1));dp[0][x]max(dp[0][x],mkp(dp[1][x].firstw,dp[1][x].second1));dp[0][x]max(dp[0][x],mkp(dp[2][x].firstw,dp[2][x].second1));return;
}signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifmemset(fi,-1,sizeof(fi));cnt-1;nread();mread()1;for(int i1;in;i){int xread(),yread(),wread();addline(x,y,w);addline(y,x,w);}ll st-inf,edinf;while(sted){ll mid(sted)1;wmid;dfs(1,0);if(dp[0][1].secondm) edmid;else stmid1;}wst;debug(w%lld\n,w);dfs(1,0);printf(%lld\n,dp[0][1].first-m*w);return 0;
}
