結果

問題 No.1221 木 *= 3
ユーザー LayCurse
提出日時 2020-09-04 21:42:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 32 ms / 2,000 ms
コード長 7,960 bytes
コンパイル時間 2,822 ms
コンパイル使用メモリ 215,992 KB
最終ジャッジ日時 2025-01-14 05:23:50
ジャッジサーバーID
(参考情報)
judge3 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
void *wmem;
char memarr[96000000];
template<class S, class T> inline S max_L(S a,T b){
return a>=b?a:b;
}
template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
(*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
(*arr)=(T*)(*mem);
(*mem)=((*arr)+x);
}
inline int my_getchar_unlocked(){
static char buf[1048576];
static int s = 1048576;
static int e = 1048576;
if(s == e && e == 1048576){
e = fread_unlocked(buf, 1, 1048576, stdin);
s = 0;
}
if(s == e){
return EOF;
}
return buf[s++];
}
inline void rd(int &x){
int k;
int m=0;
x=0;
for(;;){
k = my_getchar_unlocked();
if(k=='-'){
m=1;
break;
}
if('0'<=k&&k<='9'){
x=k-'0';
break;
}
}
for(;;){
k = my_getchar_unlocked();
if(k<'0'||k>'9'){
break;
}
x=x*10+k-'0';
}
if(m){
x=-x;
}
}
struct MY_WRITER{
char buf[1048576];
int s;
int e;
MY_WRITER(){
s = 0;
e = 1048576;
}
~MY_WRITER(){
if(s){
fwrite_unlocked(buf, 1, s, stdout);
}
}
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
MY_WRITER_VAR.s = 0;
}
MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
my_putchar_unlocked(a);
}
inline void wt_L(int x){
int s=0;
int m=0;
char f[10];
if(x<0){
m=1;
x=-x;
}
while(x){
f[s++]=x%10;
x/=10;
}
if(!s){
f[s++]=0;
}
if(m){
my_putchar_unlocked('-');
}
while(s--){
my_putchar_unlocked(f[s]+'0');
}
}
inline void wt_L(unsigned x){
int s=0;
char f[10];
while(x){
f[s++]=x%10;
x/=10;
}
if(!s){
f[s++]=0;
}
while(s--){
my_putchar_unlocked(f[s]+'0');
}
}
inline void wt_L(long long x){
int s=0;
int m=0;
char f[20];
if(x<0){
m=1;
x=-x;
}
while(x){
f[s++]=x%10;
x/=10;
}
if(!s){
f[s++]=0;
}
if(m){
my_putchar_unlocked('-');
}
while(s--){
my_putchar_unlocked(f[s]+'0');
}
}
inline void wt_L(unsigned long long x){
int s=0;
char f[21];
while(x){
f[s++]=x%10;
x/=10;
}
if(!s){
f[s++]=0;
}
while(s--){
my_putchar_unlocked(f[s]+'0');
}
}
int WRITER_DOUBLE_DIGIT = 15;
inline int writerDigit_double(){
return WRITER_DOUBLE_DIGIT;
}
inline void writerDigit_double(int d){
WRITER_DOUBLE_DIGIT = d;
}
inline void wt_L(double x){
const int d = WRITER_DOUBLE_DIGIT;
int k;
int r;
double v;
if(x!=x || (x==x+1 && x==2*x)){
my_putchar_unlocked('E');
my_putchar_unlocked('r');
my_putchar_unlocked('r');
return;
}
if(x < 0){
my_putchar_unlocked('-');
x = -x;
}
x += 0.5 * pow(0.1, d);
r = 0;
v = 1;
while(x >= 10*v){
v *= 10;
r++;
}
while(r >= 0){
r--;
k = floor(x / v);
if(k >= 10){
k = 9;
}
if(k <= -1){
k = 0;
}
x -= k * v;
v *= 0.1;
my_putchar_unlocked(k + '0');
}
if(d > 0){
my_putchar_unlocked('.');
v = 1;
for(r=(0);r<(d);r++){
v *= 0.1;
k = floor(x / v);
if(k >= 10){
k = 9;
}
if(k <= -1){
k = 0;
}
x -= k * v;
my_putchar_unlocked(k + '0');
}
}
}
inline void wt_L(const char c[]){
int i=0;
for(i=0;c[i]!='\0';i++){
my_putchar_unlocked(c[i]);
}
}
inline void wt_L(string &x){
int i=0;
for(i=0;x[i]!='\0';i++){
my_putchar_unlocked(x[i]);
}
}
struct graph{
int N;
int *es;
int **edge;
void setEdgeRootedTree(int N__, int M, int A[], int B[], int root=0, int reorder=0, int cnv[] = NULL, void **mem = &wmem){
int i;
int j;
int k;
int *dist;
int *q;
int qs;
int qe;
int *ind;
void *tmem;
N = N__;
tmem = ((char*)(*mem)) + (sizeof(int) * N + 15) + (sizeof(int*) * N + 15) + (sizeof(int) * M + 15 * N);
walloc1d(&es, N, mem);
walloc1d(&edge, N, mem);
for(i=(0);i<(N);i++){
es[i] = 0;
}
for(i=(0);i<(M);i++){
es[A[i]]++;
es[B[i]]++;
}
for(i=(0);i<(N);i++){
walloc1d(&edge[i], es[i], &tmem);
}
for(i=(0);i<(N);i++){
es[i] = 0;
}
for(i=(0);i<(M);i++){
edge[A[i]][es[A[i]]++] = B[i];
edge[B[i]][es[B[i]]++] = A[i];
}
walloc1d(&dist, N, &tmem);
walloc1d(&q, N, &tmem);
walloc1d(&ind, N, &tmem);
if(cnv==NULL){
walloc1d(&cnv, N, &tmem);
}
for(i=(0);i<(N);i++){
dist[i] = -1;
}
dist[root] = 0;
qs = qe = 0;
q[qe++] = root;
while(qs < qe){
i = q[qs++];
for(j=(0);j<(es[i]);j++){
k = edge[i][j];
if(dist[k]==-1){
dist[k] = dist[i] + 1;
q[qe++] = k;
}
}
}
if(reorder == 0){
for(i=(0);i<(N);i++){
cnv[i] = i;
}
for(i=(0);i<(N);i++){
ind[i] = i;
}
}
else{
for(i=(0);i<(N);i++){
cnv[i] = q[i];
}
for(i=(0);i<(N);i++){
ind[cnv[i]] = i;
}
}
for(i=(0);i<(N);i++){
es[i] = 0;
}
for(i=(0);i<(M);i++){
j = A[i];
k = B[i];
if(dist[j] > dist[k]){
swap(j, k);
}
es[ind[j]]++;
}
for(i=(0);i<(N);i++){
walloc1d(&edge[i], es[i], mem);
}
for(i=(0);i<(N);i++){
es[i] = 0;
}
for(i=(0);i<(M);i++){
j = A[i];
k = B[i];
if(dist[j] > dist[k]){
swap(j, k);
}
j = ind[j];
k = ind[k];
edge[j][es[j]++] = k;
}
}
int preorder(int res[], int root = 0, void *mem=wmem){
int i;
int j;
int k;
int sts;
int sz = 0;
long long *st;
char *vis;
walloc1d(&vis, N, &mem);
walloc1d(&st, N, &mem);
sts = 0;
st[sts++] = ((long long)root) << 32;
for(i=(0);i<(N);i++){
vis[i] = 0;
}
vis[root] = 1;
while(sts){
i = st[--sts] >> 32;
j = st[sts] & 2147483647;
if(j==0){
res[sz++] = i;
}
while(j < es[i]){
k = edge[i][j++];
if(vis[k]){
continue;
}
if(j < es[i]){
st[sts++] = (((long long)i) << 32) + j;
}
vis[k] = 1;
st[sts++] = ((long long)k) << 32;
break;
}
}
return sz;
}
}
;
int N;
int A[100000];
int B[100000];
int U[100000];
int V[100000];
long long dp[2][100000];
graph g;
int pre[100000];
int main(){
int t_ynMSdg;
wmem = memarr;
rd(N);
{
int Lj4PdHRW;
for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){
rd(A[Lj4PdHRW]);
}
}
{
int e98WHCEY;
for(e98WHCEY=(0);e98WHCEY<(N);e98WHCEY++){
rd(B[e98WHCEY]);
}
}
{
int FmcKpFmN;
for(FmcKpFmN=(0);FmcKpFmN<(N-1);FmcKpFmN++){
rd(U[FmcKpFmN]);U[FmcKpFmN] += (-1);
rd(V[FmcKpFmN]);V[FmcKpFmN] += (-1);
}
}
g.setEdgeRootedTree(N,N-1,U,V);
g.preorder(pre);
for(t_ynMSdg=(N)-1;t_ynMSdg>=(0);t_ynMSdg--){
int tU__gIr_;
auto &i = pre[t_ynMSdg];
dp[0][i] = 0;
dp[1][i] = A[i];
for(tU__gIr_=(0);tU__gIr_<(g.es[i]);tU__gIr_++){
auto &j = g.edge[i][tU__gIr_];
dp[0][i] +=max_L(dp[0][j]+B[i]+B[j], dp[1][j]);
dp[1][i] +=max_L(dp[0][j], dp[1][j]);
}
}
wt_L(max_L(dp[0][0], dp[1][0]));
wt_L('\n');
return 0;
}
// cLay varsion 20200813-1 [beta]
// --- original code ---
// int N, A[1d5], B[1d5], U[1d5], V[1d5];
// ll dp[2][1d5];
// graph g;
// int pre[1d5];
// {
// rd(N,A(N),B(N),(U--,V--)(N-1));
// g.setEdgeRootedTree(N,N-1,U,V);
// g.preorder(pre);
//
// rrep[pre](i,N){
// dp[0][i] = 0;
// dp[1][i] = A[i];
// rep[g.edge[i]](j,g.es[i]){
// dp[0][i] += max(dp[0][j]+B[i]+B[j], dp[1][j]);
// dp[1][i] += max(dp[0][j], dp[1][j]);
// }
// }
// wt(max(dp[0][0],dp[1][0]));
// }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0