ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#205203 | #3672. 20240629_A | nullptr_qwq | 100 | 11272ms | 73804kb | C++11 | 4.2kb | 2024-06-29 10:51:29 | 2024-06-29 13:04:07 |
answer
// 私は猫です
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define dF(i,a,b) for(int i=(a);i>=(b);i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
using namespace std;
ll read(){
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
inline void chkmin(int &x,int y){ x=min(x,y); }
inline void chkmax(int &x,int y){ x=max(x,y); }
const int mod=998244353,maxn=300005;
int fir[maxn],euler_seq[maxn],dep[maxn],Timer,n;
int rev[maxn],dfn[maxn],tim,fa[maxn],top[maxn],siz[maxn],son[maxn];
vector<int>g[maxn];
void init_dfs(int u,int f=0){
dep[u]=dep[f]+1,euler_seq[fir[u]=++Timer]=u,fa[u]=f,siz[u]=1,son[u]=0;
for(auto it=g[u].begin();it!=g[u].end();++it){
const int v=*it;
if(v==f)continue;
init_dfs(v,u),euler_seq[++Timer]=u,siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
void dfs2(int u,int t=1){
rev[dfn[u]=++tim]=u,top[u]=t;
if(!son[u])return;
dfs2(son[u],t);
for(auto it=g[u].begin();it!=g[u].end();++it){
const int v=*it;
if(v^fa[u]&&v^son[u]) dfs2(v,v);
}
}
namespace getlca{
int mn[maxn][21];
void lca_init(){
F(i,1,n<<1) mn[i][0]=euler_seq[i];
F(j,1,20) F(i,1,(n<<1)-(1<<j)+1){
int L=mn[i][j-1],R=mn[i+(1<<(j-1))][j-1];
mn[i][j]=(dep[L]<dep[R])?L:R;
}
}
int lca(int u,int v){
int l=fir[u],r=fir[v];
if(l>r) swap(l,r);
int t=__lg(r-l+1),L=mn[l][t],R=mn[r-(1<<t)+1][t];
return dep[L]<dep[R]?L:R;
}
}
using getlca::lca;
int dist(int u,int v){ return dep[u]+dep[v]-(dep[lca(u,v)]<<1)+1; }
int rt[maxn];
namespace seg1{
int ls[maxn<<5],rs[maxn<<5],t[maxn<<5],tot=0;
void update(int &o,int pre,int l,int r,int pos){
o=++tot;
ls[o]=ls[pre],rs[o]=rs[pre],t[o]=t[pre]+1;
if(l==r) return;
int mid=(l+r)>>1;
(pos<=mid)?update(ls[o],ls[pre],l,mid,pos):update(rs[o],rs[pre],mid+1,r,pos);
}
int query(int u,int v,int u1,int v1,int l,int r,int k){
if(l==r)return l;
int mid=(l+r)>>1;
int cnt=t[rs[u]]+t[rs[v]]-t[rs[u1]]-t[rs[v1]];
if(cnt>=k)return query(rs[u],rs[v],rs[u1],rs[v1],mid+1,r,k);
return query(ls[u],ls[v],ls[u1],ls[v1],l,mid,k-cnt);
}
void clear(){
F(i,1,tot)ls[i]=rs[i]=t[i]=0;
tot=0;
}
}
void dfs1(int u,int f=0){
seg1::update(rt[u],rt[f],1,n,u);
for(auto it=g[u].begin();it!=g[u].end();++it){
const int v=*it;
if(v^f)dfs1(v,u);
}
}
vector<pair<int,int>>vec[maxn];
namespace seg{
#define lc (o<<1)
#define rc (o<<1|1)
int t[maxn<<2];
void init(){ memset(t,0,sizeof t); }
void update(int o,int l,int r,int ql,int qr){
if(ql<=l&&qr>=r)return ++t[o],void();
int mid=(l+r)>>1;
if(ql<=mid)update(lc,l,mid,ql,qr);
if(qr>mid) update(rc,mid+1,r,ql,qr);
}
int query(int o,int l,int r,int pos){
if(l==r)return t[o];
int mid=(l+r)>>1;
return ((pos<=mid)?query(lc,l,mid,pos):query(rc,mid+1,r,pos))+t[o];
}
}
void update(int u,int v){
for(;top[u]^top[v];u=fa[top[u]]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
seg::update(1,1,n,dfn[top[u]],dfn[u]);
}
if(dfn[u]>dfn[v])swap(u,v);
seg::update(1,1,n,dfn[u],dfn[v]);
}
void solve(){
n=read(),tim=Timer=0,seg1::clear();
F(i,1,n) g[i].clear(),rt[i]=0,vec[i].clear();
F(i,1,n-1){
int u=read(),v=read();
g[u].push_back(v),g[v].push_back(u);
}init_dfs(1),getlca::lca_init(),dfs1(1),dfs2(1);
int cmh=read();
F(i,1,cmh){
int u=read(),v=read(),k=read();
chkmin(k,dist(u,v));
const int t=lca(u,v);
int x=seg1::query(rt[u],rt[v],rt[t],rt[fa[t]],1,n,k);
// printf("path=(%d,%d) k=%d kthmax=%d\n",u,v,k,x);
vec[x].push_back(mkp(u,v));
}
seg::init();
F(i,1,n){
for(auto it=vec[i].begin();it!=vec[i].end();++it){
const int u=it->first,v=it->second;
update(u,v);
}
printf("%d ",seg::query(1,1,n,dfn[i]));
}
puts("");
}
signed main(){
int sjy=read();
cmh(sjy) solve();
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 18ms
memory: 21224kb
input:
5 2073 975 1275 1890 1275 322 1275 215 1275 781 1275 789 1275 1362 1275 43 1275 1350 1275 1982 1275 ...
output:
4 4 2 3 2 3 2 4 5 4 3 3 3 2 5 0 4 4 2 3 5 5 3 5 4 4 5 1 2 3 2 4 2 5 1 5 5 3 2 2 1 5 13 1 0 1 5 1 2 1...
result:
ok 11560 numbers
Test #2:
score: 10
Accepted
time: 23ms
memory: 21288kb
input:
5 2756 520 1572 1068 1572 1754 1572 726 1572 1416 1572 1719 1572 2207 1572 613 1572 1327 1572 1626 1...
output:
2 1 2 4 1 1 2 2 2 4 2 1 4 2 3 0 0 2 2 2 2 2 1 2 2 1 0 0 2 1 4 1 2 6 2 1 4 3 1 3 2 1 1 0 1 3 3 3 1 5 ...
result:
ok 11691 numbers
Test #3:
score: 10
Accepted
time: 16ms
memory: 21376kb
input:
5 2420 2025 1800 84 1800 38 1800 1223 1800 1873 1800 1618 1800 1952 1800 50 1800 431 1800 243 1800 1...
output:
2 2 2 4 3 2 3 2 1 3 3 2 1 0 1 2 2 0 1 1 0 0 1 4 2 1 3 1 0 3 3 0 2 2 3 3 4 196 3 4 2 1 2 1 2 5 5 5 3 ...
result:
ok 12499 numbers
Test #4:
score: 10
Accepted
time: 1566ms
memory: 72848kb
input:
5 98586 10316 68865 53310 10316 67839 53310 7829 67839 17428 7829 60346 17428 52285 60346 18272 5228...
output:
3351 1009 2388 3449 3392 3343 3395 1674 3368 3344 3170 1992 3386 2205 2865 3312 1789 1026 2358 3301 ...
result:
ok 479564 numbers
Test #5:
score: 10
Accepted
time: 1541ms
memory: 73804kb
input:
5 95990 21900 49492 62026 21900 25956 62026 69043 25956 65040 69043 26119 65040 84298 26119 63833 84...
output:
888 2917 2819 3297 2464 375 346 730 2920 3326 3322 2289 3268 3208 3173 432 1727 2929 3303 1243 3171 ...
result:
ok 472548 numbers
Test #6:
score: 10
Accepted
time: 2236ms
memory: 72284kb
input:
5 95974 53512 9795 37335 53512 1203 37335 10494 1203 93049 10494 9200 93049 20837 9200 9275 20837 38...
output:
2457 3550 354 3610 1667 3254 3533 3631 3708 3255 3353 1624 3731 1104 922 3703 566 3685 1996 2457 372...
result:
ok 468013 numbers
Test #7:
score: 10
Accepted
time: 1458ms
memory: 70012kb
input:
5 93822 79054 63550 34185 63550 42633 63550 85615 63550 55294 63550 36970 63550 23207 63550 78235 63...
output:
1 4 6 4 2 0 4 1 2 1 0 1 3 2 1 2 3 2 0 3 5 4 1 0 1 1 5 1 0 2 0 0 0 0 1 2 0 3 2 2 0 2 3 1 0 3 2 2 1 2 ...
result:
ok 476957 numbers
Test #8:
score: 10
Accepted
time: 1711ms
memory: 70260kb
input:
5 92650 79078 77548 9254 77548 5721 77548 66152 77548 74853 77548 79994 77548 77671 77548 33441 7754...
output:
2 2 3 4 1 4 2 0 0 2 3 1 3 3 2 1 2 2 1 1 2 3 2 178 5 4 0 2 2 2 2 5 2 2 2 2 2 2 4 3 0 3 3 4 2 2 2 3 8 ...
result:
ok 464906 numbers
Test #9:
score: 10
Accepted
time: 1382ms
memory: 70960kb
input:
5 99464 84000 97248 35816 97248 35532 97248 288 97248 13305 97248 25485 97248 8820 97248 55412 97248...
output:
1 2 2 2 1 2 2 1 1 1 4 5 1 3 1 1 1 3 3 2 4 2 3 4 2 0 3 0 2 5 1 2 2 1 3 4 0 0 2 2 1 2 4 1 0 2 1 3 4 2 ...
result:
ok 482187 numbers
Test #10:
score: 10
Accepted
time: 1321ms
memory: 70204kb
input:
5 97896 76127 67529 49658 67529 86214 67529 56010 67529 63791 67529 41600 67529 43052 67529 76542 67...
output:
3 2 3 2 3 4 1 2 1 2 2 2 3 2 4 4 2 2 3 1 0 3 1 2 3 3 3 4 1 2 2 2 4 2 2 1 1 4 1 4 1 3 2 3 2 3 2 2 4 3 ...
result:
ok 474058 numbers
Extra Test:
score: 0
Extra Test Passed