QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#126751 | #6738. Cover | csy2005 | AC ✓ | 712ms | 173560kb | C++14 | 3.5kb | 2023-07-18 22:28:39 | 2023-07-18 22:29:25 |
Judging History
answer
#include <bits/stdc++.h>
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(((long long)(n))-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();++itr)
#define spln(i,n) (i==n?'\n':' ')
using namespace std;
typedef long long i64;
inline void read(int &x)
{
char c;int f=1;
while(!isdigit(c=getchar()))if(c=='-')f=-1;
x=(c&15);while(isdigit(c=getchar()))x=(x<<1)+(x<<3)+(c&15);
x*=f;
}
inline void read(i64 &x)
{
char c;int f=1;
while(!isdigit(c=getchar()))if(c=='-')f=-1;
x=(c&15);while(isdigit(c=getchar()))x=(x<<1)+(x<<3)+(c&15);
x*=f;
}
int typ,_;
int n,m,i,j;
vector<int> bi[100005],v[100005];
int fa[100005],id[100005],sz[100005],tp[100005],son[100005],dfn[100005],ti,mp[100005],dep[100005];
int px[500005],py[500005],plca[500005],plx[500005],ply[500005];i64 pv[500005];
void dfs1(int x,int p)
{
sz[x]=1;fa[x]=p;int c=0;
if(p) bi[x].erase(find(bi[x].begin(),bi[x].end(),p));
ff(bi[x],it){id[*it]=c++;dep[*it]=dep[x]+1;dfs1(*it,x);sz[x]+=sz[*it];if(!son[x]||sz[son[x]]<sz[*it])son[x]=*it;}
}
void dfs2(int x,int t)
{
mp[dfn[x]=++ti]=x;tp[x]=t;
if(son[x])dfs2(son[x],t);
ff(bi[x],it)if(*it!=son[x])dfs2(*it,*it);
}
int lca(int x,int y)
{
while(tp[x]!=tp[y]){if(dep[tp[x]]<dep[tp[y]])swap(x,y);x=fa[tp[x]];}
return mp[min(dfn[x],dfn[y])];
}
int gtp(int x,int d)
{
if(dep[x]<d) return x;
while(dep[tp[x]]>d) x=fa[tp[x]];
return mp[dfn[x]-(dep[x]-d)];
}
struct bit
{
i64 s[500005];
void add(int x,i64 c){while(x<=n) s[x]+=c,x+=(x&-x);}
i64 query(int x){i64 c=0;while(x) c+=s[x],x&=(x-1);return c;}
}t1;
i64 query1(int x)
{
i64 s=0;
while(x){
s+=t1.query(dfn[x])-t1.query(dfn[tp[x]]-1);
x=fa[tp[x]];
}
return s;
}
vector<i64> f[100005];
i64 g[20][20],g0[20];
i64 h[100005];
void dfs3(int x)
{
// cerr<<x<<": ";ff(bi[x],it)cerr<<*it<<' ';cerr<<endl;
int i,j,k,len=bi[x].size();ff(bi[x],it) dfs3(*it);
memset(g,0,sizeof(g));memset(g0,0,sizeof(g0));
ff(bi[x],it){
assert(id[*it]<=_);
g0[id[*it]]=max(g0[id[*it]],f[*it].back());
}
ff(v[x],it){
pv[*it]+=query1(px[*it])+(px[*it]==x?0:f[px[*it]].back());
pv[*it]+=query1(py[*it])+(py[*it]==x?0:f[py[*it]].back());
if(px[*it]==x){
g0[id[ply[*it]]]=max(g0[id[ply[*it]]],pv[*it]);
}
else if(py[*it]==x){
g0[id[plx[*it]]]=max(g0[id[plx[*it]]],pv[*it]);
}
else{
g[id[plx[*it]]][id[ply[*it]]]=g[id[ply[*it]]][id[plx[*it]]]=max(g[id[plx[*it]]][id[ply[*it]]],pv[*it]);
}
}
f[x].resize(1<<len);
fz1(i,(1<<len)-1){
j=len-1;while(!((i>>j)&1))j--;
f[x][i]=max(f[x][i],f[x][i^(1<<j)]+g0[j]);
fz0k(k,j)if((i>>k)&1) f[x][i]=max(f[x][i],f[x][i^(1<<j)^(1<<k)]+g[j][k]);
}
fz0k(i,len){
h[bi[x][i]]=f[x][(1<<len)-1-(1<<i)];
t1.add(dfn[bi[x][i]],h[bi[x][i]]);
}
}
int main()
{
read(n);read(m);read(_);fz1(i,n-1){int x,y;read(x);read(y);bi[x].push_back(y);bi[y].push_back(x);}
int rt;fz1(i,n){assert(bi[i].size()<=_);if(bi[i].size()==1)rt=i;}
dfs1(rt,0);dfs2(rt,rt);
fz1(i,m) read(px[i]),read(py[i]),read(pv[i]),assert(px[i]!=py[i]),v[plca[i]=lca(px[i],py[i])].push_back(i),plx[i]=gtp(px[i],dep[plca[i]]+1),ply[i]=gtp(py[i],dep[plca[i]]+1);
dfs3(rt);
printf("%lld\n",f[rt].back());
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 25444kb
input:
5 7 3 1 2 1 3 2 4 2 5 3 2 8 5 4 10 3 1 2 1 2 7 2 1 2 1 2 1 5 2 3
output:
19
result:
ok 1 number(s): "19"
Test #2:
score: 0
Accepted
time: 654ms
memory: 173560kb
input:
100000 500000 12 2 1 3 2 4 2 5 2 6 5 7 2 8 5 9 3 10 2 11 2 12 5 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 12 25 2 26 2 27 2 28 2 29 2 30 15 31 30 32 23 33 26 34 22 35 30 36 26 37 3 38 3 39 3 40 3 41 3 42 3 43 3 44 3 45 3 46 3 47 20 48 21 49 4 50 4 51 4 52 4 53 4 54 4 55 4 56 4 57 4 5...
output:
660925834533
result:
ok 1 number(s): "660925834533"
Test #3:
score: 0
Accepted
time: 712ms
memory: 173480kb
input:
100000 500000 12 2 1 3 2 4 1 5 4 6 2 7 5 8 2 9 7 10 8 11 3 12 11 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 22 24 8 25 2 26 2 27 2 28 2 29 2 30 2 31 2 32 2 33 26 34 27 35 23 36 13 37 3 38 3 39 3 40 3 41 3 42 3 43 3 44 3 45 3 46 3 47 14 48 8 49 4 50 4 51 4 52 4 53 4 54 4 55 4 56 4 57 4 58 4...
output:
664434138007
result:
ok 1 number(s): "664434138007"
Test #4:
score: 0
Accepted
time: 691ms
memory: 173536kb
input:
100000 500000 12 2 1 3 1 4 2 5 3 6 4 7 2 8 7 9 2 10 6 11 4 12 8 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 13 24 23 25 2 26 2 27 2 28 2 29 2 30 2 31 2 32 2 33 26 34 31 35 33 36 33 37 3 38 3 39 3 40 3 41 3 42 3 43 3 44 3 45 3 46 3 47 34 48 16 49 4 50 4 51 4 52 4 53 4 54 4 55 4 56 4 57 4 58 ...
output:
639691495391
result:
ok 1 number(s): "639691495391"
Test #5:
score: 0
Accepted
time: 705ms
memory: 173424kb
input:
100000 500000 12 2 1 3 1 4 2 5 1 6 5 7 4 8 2 9 1 10 4 11 8 12 7 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 14 22 14 23 21 24 20 25 2 26 2 27 2 28 2 29 2 30 2 31 2 32 2 33 2 34 23 35 31 36 7 37 3 38 3 39 3 40 3 41 3 42 3 43 3 44 3 45 3 46 3 47 3 48 29 49 4 50 4 51 4 52 4 53 4 54 4 55 4 56 4 57 4 58 3...
output:
662244733768
result:
ok 1 number(s): "662244733768"
Test #6:
score: 0
Accepted
time: 694ms
memory: 171368kb
input:
100000 500000 12 2 1 3 1 4 1 5 1 6 3 7 1 8 4 9 3 10 7 11 2 12 5 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 14 21 12 22 11 23 9 24 20 25 2 26 2 27 2 28 2 29 2 30 2 31 2 32 2 33 2 34 2 35 14 36 30 37 3 38 3 39 3 40 3 41 3 42 3 43 3 44 3 45 3 46 24 47 38 48 35 49 4 50 4 51 4 52 4 53 4 54 4 55 4 56 4 57 4 58...
output:
669458090009
result:
ok 1 number(s): "669458090009"
Test #7:
score: 0
Accepted
time: 158ms
memory: 39624kb
input:
100000 500000 12 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 ...
output:
488921502446
result:
ok 1 number(s): "488921502446"
Test #8:
score: 0
Accepted
time: 191ms
memory: 40564kb
input:
100000 500000 12 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 16 41 40 42 41 43 42 44 33 45 44 46 45 47 46 48 47 49 48 50 49 51 50 ...
output:
468137226275
result:
ok 1 number(s): "468137226275"
Test #9:
score: 0
Accepted
time: 202ms
memory: 38360kb
input:
100000 500000 12 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 35 51 50 ...
output:
483733769728
result:
ok 1 number(s): "483733769728"
Test #10:
score: 0
Accepted
time: 171ms
memory: 41256kb
input:
100000 500000 12 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 ...
output:
478945297872
result:
ok 1 number(s): "478945297872"
Test #11:
score: 0
Accepted
time: 188ms
memory: 39544kb
input:
100000 500000 12 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 ...
output:
489443708266
result:
ok 1 number(s): "489443708266"
Test #12:
score: 0
Accepted
time: 126ms
memory: 30904kb
input:
10000 500000 12 2 1 3 2 4 1 5 1 6 2 7 5 8 2 9 8 10 6 11 8 12 4 13 11 14 1 15 6 16 5 17 10 18 17 19 12 20 8 21 16 22 1 23 5 24 21 25 23 26 3 27 18 28 6 29 8 30 15 31 1 32 30 33 17 34 23 35 5 36 24 37 33 38 25 39 34 40 1 41 24 42 11 43 6 44 18 45 28 46 25 47 32 48 40 49 29 50 43 51 33 52 9 53 2 54 20 ...
output:
560772428222
result:
ok 1 number(s): "560772428222"
Test #13:
score: 0
Accepted
time: 145ms
memory: 32212kb
input:
10000 500000 12 2 1 3 2 4 2 5 2 6 4 7 5 8 4 9 4 10 4 11 4 12 10 13 5 14 13 15 9 16 15 17 2 18 5 19 14 20 11 21 11 22 20 23 20 24 1 25 5 26 15 27 20 28 17 29 4 30 18 31 12 32 14 33 18 34 18 35 16 36 31 37 18 38 19 39 12 40 17 41 14 42 7 43 27 44 25 45 13 46 35 47 10 48 15 49 46 50 44 51 21 52 15 53 2...
output:
572767352204
result:
ok 1 number(s): "572767352204"
Test #14:
score: 0
Accepted
time: 134ms
memory: 31552kb
input:
10000 500000 12 2 1 3 1 4 2 5 2 6 2 7 4 8 7 9 7 10 2 11 9 12 3 13 1 14 7 15 9 16 8 17 2 18 13 19 12 20 2 21 16 22 8 23 13 24 8 25 20 26 25 27 14 28 4 29 28 30 4 31 12 32 13 33 24 34 1 35 21 36 5 37 16 38 28 39 35 40 28 41 13 42 20 43 19 44 16 45 40 46 28 47 3 48 5 49 14 50 2 51 4 52 47 53 47 54 15 5...
output:
585482767864
result:
ok 1 number(s): "585482767864"
Test #15:
score: 0
Accepted
time: 151ms
memory: 31976kb
input:
10000 500000 12 2 1 3 2 4 3 5 3 6 3 7 5 8 7 9 4 10 3 11 2 12 7 13 4 14 8 15 9 16 1 17 12 18 13 19 2 20 3 21 16 22 10 23 20 24 4 25 19 26 6 27 17 28 5 29 17 30 27 31 22 32 14 33 11 34 4 35 24 36 34 37 14 38 23 39 18 40 30 41 28 42 36 43 12 44 5 45 14 46 17 47 11 48 14 49 16 50 16 51 18 52 30 53 17 54...
output:
564574799774
result:
ok 1 number(s): "564574799774"
Test #16:
score: 0
Accepted
time: 150ms
memory: 32192kb
input:
10000 500000 12 2 1 3 1 4 2 5 2 6 4 7 6 8 5 9 8 10 7 11 7 12 5 13 1 14 5 15 11 16 9 17 3 18 4 19 10 20 8 21 2 22 11 23 18 24 10 25 8 26 16 27 22 28 11 29 20 30 12 31 4 32 19 33 27 34 6 35 1 36 24 37 18 38 30 39 32 40 10 41 9 42 15 43 34 44 27 45 34 46 7 47 34 48 39 49 32 50 13 51 11 52 38 53 17 54 5...
output:
575291114848
result:
ok 1 number(s): "575291114848"