UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#205203#3672. 20240629_Anullptr_qwq10011272ms73804kbC++114.2kb2024-06-29 10:51:292024-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