QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#368243 | #6350. MIT | ppip | TL | 3ms | 38460kb | C++14 | 4.7kb | 2024-03-26 22:19:19 | 2024-03-26 22:19:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
constexpr int S1=1<<20;
char buf1[S1],*l1,*r1;
#define getchar() ((l1==r1&&(r1=(l1=buf1)+fread(buf1,1,S1,stdin)),l1!=r1)?*l1++:EOF)
template<typename T=int>inline T read()
{
T x=0;
char c=getchar();
while(c<'0'||c>'9')
c=getchar();
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x;
}
constexpr int S2=1<<20;
char buf2[S2],*l2=buf2;
#define putchar(c) (l2==buf2+S2&&(fwrite(buf2,1,S2,stdout),l2=buf2),*l2++=(c))
int _st[22];
template<typename T>inline void write(T x)
{
int tp=0;
do
_st[++tp]=x%10;
while(x/=10);
while(tp)
putchar(_st[tp--]+'0');
putchar(' ');
}
constexpr int N(1e6);
using LL=long long;
pair<int,int> E[N*2];
int beg[N+5];
int fa[N+5],d[N+5],lb[N+5];
int L[N+5],R[N+5],fz[N+5],sz[N+5];
LL h[N+5];
void init(int u,int fa) {
::fa[u]=fa;
d[u]=d[fa]+1;
sz[u]=1;
static int lda{0};
L[u]=++lda;
fz[lda]=u;
int p{fa},q{lb[p]},r{lb[q]};
lb[u]=(d[p]-d[q]!=d[q]-d[r]?p:r);
for (int _{beg[u]+1};_<=beg[u+1];++_) {
auto [v,w]{E[_]};
if (v==fa) continue;
h[v]=h[u]+w;
init(v,u);
sz[u]+=sz[v];
}
R[u]=lda;
}
int jump(int u,int de) {
while (d[u]>de) {
if (d[lb[u]]<de) u=fa[u];
else u=lb[u];
}
return u;
}
int LCA(int u,int v) {
if (d[u]<d[v]) swap(u,v);
u=jump(u,d[v]);
while (u!=v)
if (lb[u]==lb[v]) u=fa[u],v=fa[v];
else u=lb[u],v=lb[v];
return u;
}
bool isson(int u,int v) { return L[u]<=L[v]&&L[v]<=R[u]; }
LL dis(int u,int v) {
return h[u]+h[v]-2*h[LCA(u,v)];
}
int n;
int cen;
LL ans;
namespace S {
LL t[N<<1],tg[N<<1];
void plant() {
for (int i{1};i<=n;++i) t[i+n-1]=dis(fz[i],cen),ans+=t[i+n-1];
for (int i{n-1};i>=1;--i) t[i]=min(t[i<<1],t[i<<1|1]);
}
void up(int p) {
p+=n-1;
while (p>>=1) t[p]=min(t[p<<1],t[p<<1|1])+tg[p];
}
int query() {
int x{1};
while (x<n) {
if (t[x]==t[x<<1]+tg[x]) x<<=1;
else x=x<<1|1;
}
return x-n+1;
}
void tag(int p,LL k) {
t[p]+=k;
tg[p]+=k;
}
void modify(int l,int r,LL v) {
int l0{l},r0{r};
for (l+=n-1,r+=n-1;l<=r;l>>=1,r>>=1) {
if (l&1) t[l]+=v,tg[l]+=v,++l;
if (~r&1) t[r]+=v,tg[r]+=v,--r;
}
up(l0);up(r0);
}
}
namespace F {
int t[N+5];
void init() {
for (int i{1};i<=n;++i) {
t[i]=1;
for (int j{1};j<(i&-i);j<<=1) t[i]+=t[i-j];
}
}
void add(int x) {
for (;x<=n;x+=x&-x) --t[x];
}
int qry(int u) {
int l{L[u]-1},r{R[u]},ans{0};
while (r>l) ans+=t[r],r&=r-1;
while (l>r) ans-=t[l],l&=l-1;
return ans;
}
int kth(int k,int x=0) {
for (;x;x&=x-1) k+=t[x];
for (int i{19};i>=0;--i)
if ((x|1<<i)<=n&&t[x|1<<i]<k)
k-=t[x|=1<<i];
return fz[x+1];
}
}
namespace D {
int f[N+5],g[N+5];
void init() {
iota(f,f+2+n,0);
iota(g,g+2+n,0);
}
void del(int u) {
f[u]=u+1;
g[u]=u-1;
}
int nxt(int x) {
while (f[x]!=x) x=f[x]=f[f[x]];
return (x==n+1?0:fz[x]);
}
int pre(int x) {
while (g[x]!=x) x=g[x]=g[g[x]];
return fz[x];
}
}
bool son(int u,int v) { return L[u]<=L[v]&&L[v]<=R[u]; }
int centroid(int k) {
if (k%2==0) return cen;
int sz{F::qry(cen)};
if (sz==k/2) {
int w{D::nxt(1)},x{D::pre(L[cen]-1)},y{D::nxt(R[cen]+1)},z{D::pre(n)};
if (!y) {
int U{LCA(w,x)};
if (son(U,cen)) return LCA(x,cen);
else return U;
} else if (!x) {
int U{LCA(y,z)};
if (son(U,cen)) return LCA(y,cen);
else return U;
} else {
int l{LCA(x,cen)},r{LCA(y,cen)};
return d[l]>d[r]?l:r;
}
} else {
int u{jump(F::kth(k/2+1,L[cen]-1),d[cen]+1)};
if (F::qry(u)<=k/2) return cen;
return LCA(D::nxt(L[u]),D::pre(R[u]));
}
}
int starting_cen(int u,int fa) {
for (int _{beg[u]+1};_<=beg[u+1];++_) {
auto [v,w]{E[_]};
if (v!=fa&&sz[v]*2>n)
return starting_cen(v,u);
}
return u;
}
int U[N+5],V[N+5],W[N+5],X[N+5];
LL res[N+5];
int main() {
n=read();
for (int i{1};i<n;++i) {
U[i]=read();
V[i]=read();
W[i]=read();
++beg[U[i]];++beg[V[i]];
}
partial_sum(beg+1,beg+1+n,beg+1);
copy_n(beg+1,n,X+1);
for (int i{1};i<n;++i) E[beg[U[i]]--]={V[i],W[i]},E[beg[V[i]]--]={U[i],W[i]};
init(1,0);
cen=starting_cen(1,0);
D::init();
F::init();
S::plant();
for (int i{n-1};i>=1;--i) {
res[i+1]=ans;
int z{fz[S::query()]};
ans-=S::t[1];
D::del(L[z]);
F::add(L[z]);
S::modify(L[z],L[z],1e18);
int u{cen},v{centroid(i)};
cerr<<v<<endl;
if (u!=v) {
LL d{dis(u,v)};
ans-=d;
if (isson(v,u)) {
S::modify(L[u],R[u],2*d);
S::tag(1,-d);
} else if (isson(u,v)) {
S::modify(L[v],R[v],-2*d);
S::tag(1,d);
} else {
S::modify(L[u],R[u],d);
S::modify(L[v],R[v],-d);
}
cen=v;
}
}
for (int i{2};i<=n;i+=2) write(res[i]);
fwrite(buf2,01,l2-buf2,stdout);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 38460kb
input:
7 1 3 99 2 3 82 3 4 4 4 5 43 5 6 5 4 7 3
output:
181 280 287
result:
ok 3 number(s): "181 280 287"
Test #2:
score: -100
Time Limit Exceeded
input:
1000 328 12 58771429 881 504 17030494 847 622 20805817 12 922 58532669 879 929 52585738 495 726 27873950 855 17 37971674 797 941 76999719 702 610 719916 479 127 97829887 731 557 55300256 282 615 88802280 651 318 64099880 540 51 6547869 896 54 87823596 674 879 80674008 77 691 54802376 193 851 7869172...