百度站长管理平台,安卓应用市场官方版下载,酷炫网站,wordpress获取部分分类解析
第一道完全自己做出来的黑题awa #xff08;如果不算那道感觉完全是恶评的石油的话#xff09; 然而连写带调整了3.5h…
容易想到链的做法 设ancxanc_xancx表示x的祖先,disxdis_xdisx表示x到1的距离 则有#xff1a; dpvmindisv−lvdisu,u∈ancv(dpupv(dis…解析
第一道完全自己做出来的黑题awa 如果不算那道感觉完全是恶评的石油的话 然而连写带调整了3.5h…
容易想到链的做法 设ancxanc_xancx表示x的祖先,disxdis_xdisx表示x到1的距离 则有 dpvmindisv−lvdisu,u∈ancv(dpupv×(disv−disu)qvdp_v\min_{dis_v-l_vdis_u,u\in anc_v}(dp_up_v\times (dis_v-dis_u)q_vdpvdisv−lvdisu,u∈ancvmin(dpupv×(disv−disu)qv 这个就可以斜优了
然后考虑如何上树 树比较恶心的地方就是我们的队列会随着dfs分支的改变而变化 难以解决
换个思路 考虑点分治 对与当前的重心 rt 先把rt到1的那个联通块递归solve掉 然后再把联通块内rt的返祖链取下来 再dfs找到所有联通块内的其他点 按照能到达的最大高度sort一下 然后做个指针动态维护这个凸包二分更新就行了
代码
#includebits/stdc.h
using namespace std;
#define ll __int128
#define inf (n1)
//#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N2e5100;
const int M2e510500;
const double eps1e-5;
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;
}
void write(ll x){if(x0){putchar(-);x-x;}if(x9) write(x/10);putchar(0x%10);return;
}int n,m;
int debug(0);struct node{int to,nxt;ll w;
}p[N1];
int fi[N],cnt;
inline void addline(int x,int y,ll w){p[cnt](node){y,fi[x],w};fi[x]cnt;return;
}ll dp[N],P[N],Q[N],dis[N],l[N];
int fa[N],siz[N],mx[N],S,rt;
int que[N],num1;
int v[N],num2;
bool vis[N];void find(int x,int f){siz[x]1;mx[x]0;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof||vis[to]) continue;find(to,x);siz[x]siz[to];mx[x]max(mx[x],siz[to]);} mx[x]max(mx[x],S-siz[x]);if(!rt||mx[rt]mx[x]) rtx;return;
}void dfs(int x,int top){que[num1]x;//if(debug) printf(dfs:x%d f%d tot%d\n,x,f,tot);if(xtop) return;dfs(fa[x],top);return;
}#define X(o) dis[o]
#define Y(o) dp[o]
int q[N],le,ri;inline void upd(int x){int stle,edri;while(sted){int mid(sted)1,oq[mid];if(dis[x]-dis[o]l[x]||(midriP[x]*(X(q[mid1])-X(q[mid]))(Y(q[mid1])-Y(q[mid])))) stmid1;else edmid;//if(debug) printf( mid%d o%d d%lld %d||(%d%d) (%d %d)\n,mid,o,(long long)(dis[x]-dis[o]),dis[x]-dis[o]l[x],midtot,P[x]*(X(q[num1])-X(q[num]))(Y(q[num1])-Y(q[num])),st,ed);}if(steddis[x]-dis[q[st]]l[x]){int uq[st];dp[x]min(dp[x],P[x]*(dis[x]-dis[u])dp[u]Q[x]);if(debug) printf( update: x%d u%d dp%lld\n,x,u,(long long)dp[x]);}return;
}inline void add(int x){if(debug) printf( add:x%d (%lld %lld)\n,x,(long long)X(x),(long long)Y(x));while(leri(Y(q[le])-Y(x))*(X(q[le1])-X(q[le]))(Y(q[le1])-Y(q[le]))*(X(q[le])-X(x))) le;q[--le]x;if(debug) for(int ile;iri;i) printf([%d]:(%lld %lld) ,q[i],(long long)X(q[i]),(long long)Y(q[i]));if(debug) putchar(\n);return;
}void get(int x,int f){v[num2]x;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof||vis[to]) continue;get(to,x);}return;
}
int findtop(int x){return fa[x]!vis[fa[x]]?findtop(fa[x]):x;
}
int calc(int x,int f){int res(1);for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof||vis[to]) continue;rescalc(to,x);}return res;
}
bool cmp(int x,int y){return dis[x]-l[x]dis[y]-l[y];
}
void solve(int x){Scalc(x,0);rt0;find(x,0);xrt;vis[x]1;int topfindtop(x);if(debug) printf(\nsolve: %d (S%d top%d)\n,x,S,top);if(fa[x]!vis[fa[x]]){solve(fa[x]);}if(debug) printf(\nbeginwork:%d\n,x);num10;num20;dfs(x,top);for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(vis[to]||tofa[x]) continue;get(to,x);}sort(v1,v1num2,cmp);if(debug){printf(que:);for(int i1;inum1;i) printf(%d ,que[i]);putchar(\n);printf(v:);for(int i1;inum2;i) printf(%d ,v[i]);putchar(\n);}for(int i1;inum1;i){int uque[i];if(dis[x]-dis[u]l[x]) break;dp[x]min(dp[x],dp[u]P[x]*(dis[x]-dis[u])Q[x]);}int pl1;rin;len1;for(int i1;inum2;i){while(plnum1dis[v[i]]-l[v[i]]dis[que[pl]]){add(que[pl]);pl;}upd(v[i]);}for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(vis[to]) continue;solve(to);}return;
}void init(int x,int f){for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof) continue;dis[to]dis[x]p[i].w;init(to,x);}return;
}
int main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifmemset(fi,-1,sizeof(fi));cnt-1;nread();int zhennanrencongbuxiebufenfenread();//assert(zhennanrencongbuxiebufenfen3);for(int i2;in;i) dp[i]2e18;dp[1]0;for(int i2;in;i){fa[i]read();ll wread();P[i]read();Q[i]read();l[i]read();addline(fa[i],i,w);addline(i,fa[i],w);}init(1,0);siz[1]n;solve(1);for(int i2;in;i) write(dp[i]),putchar(\n);return 0;
}
/**/
