QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#217353 | #5017. 相等树链 | chenxinyang2006 | 0 | 631ms | 27636kb | C++14 | 4.2kb | 2023-10-16 19:52:52 | 2023-10-16 19:52:52 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;
template <class T>
void chkmax(T &x,T y){
if(x < y) x = y;
}
template <class T>
void chkmin(T &x,T y){
if(x > y) x = y;
}
inline int popcnt(int x){
return __builtin_popcount(x);
}
inline int ctz(int x){
return __builtin_ctz(x);
}
/*ll power(ll p,int k = mod - 2){
ll ans = 1;
while(k){
if(k % 2 == 1) ans = ans * p % mod;
p = p * p % mod;
k /= 2;
}
return ans;
}*/
int n;
int fa[200005];
int cnt;
int head[200005];
struct eg{
int to,nxt;
}edge[400005];
void make(int u,int v){
edge[++cnt].to = v;
edge[cnt].nxt = head[u];
head[u] = cnt;
}
mt19937_64 rnd(0);
ull a[200005];
int siz[200005],h[200005],inq[200005],vis[200005];
vector <int> S;
void dfs1(int u,int f){
siz[u] = 1;
inq[u] = 1;
h[u] = 0;
S.eb(u);
for(int i = head[u];i;i = edge[i].nxt){
int v = edge[i].to;
if(v == f || vis[v]) continue;
dfs1(v,u);
siz[u] += siz[v];
chkmax(h[u],siz[v]);
}
}
int N;
vector <int> G[200005];
int col[200005],dep[200005],cov[200005];
ull sum[2][200005];
int Mx[200005][2],frp[200005];
void dfs2(int u,int f){
if(cov[u] < N) frp[u] = 0;
for(int i = head[u];i;i = edge[i].nxt){
int v = edge[i].to;
if(v == f) continue;
sum[0][v] = sum[0][u] + a[v];
Mx[v][0] = Mx[u][0];Mx[v][1] = Mx[u][1];
frp[v] = frp[u];
int p = v;
if(dep[Mx[v][0]] < dep[p]) swap(p,Mx[v][0]);
if(dep[Mx[v][1]] < dep[p] && col[p] != col[Mx[v][0]]) Mx[v][1] = p;
dfs2(v,u);
}
}
void dfs3(int u,int f,int c){
cov[u] = N;
col[u] = c;
for(int v:G[u]){
if(v == f) continue;
sum[1][v] = sum[1][u] + a[v];
dep[v] = dep[u] + 1;
dfs3(v,u,c);
}
}
ll ans,answer;
map <ull,int> buc[3];
void test(ull val,int sz){
// printf("test %llu\n",val);
rep(i,0,2 - sz) ans += buc[i][-val];
buc[sz][val]++;
}
void add(int u){
// printf("add %d\n",u);
if(!frp[u]) return;
test(sum[0][u],0);
if(Mx[u][0]) test(sum[0][u] - sum[1][Mx[u][0]],1);
if(Mx[u][1]){
test(sum[0][u] - sum[1][Mx[u][1]],1);
test(sum[0][u] - sum[1][Mx[u][1]] - sum[1][Mx[u][0]],2);
}
}
void dfs4(int u,int f){
add(u);
for(int i = head[u];i;i = edge[i].nxt){
int v = edge[i].to;
if(v == f) continue;
dfs4(v,u);
}
}
void solve(int rt){
++N;
S.clear();
dfs1(rt,0);
int heavy = rt;
for(int u:S) if(max(h[u],siz[rt] - siz[u]) <= max(h[heavy],siz[rt] - siz[heavy])) heavy = u;
// printf("solve:\n");
// for(int u:S) printf("%d ",u);
// printf("\nheavy=%d\n",heavy);
for(int u:S){
if(inq[fa[u]]){
G[fa[u]].eb(u);
G[u].eb(fa[u]);
}
}
col[heavy] = 0;
cov[heavy] = N;
for(int v:G[heavy]){
dep[v] = 1;
sum[1][v] = a[v];
dfs3(v,heavy,v);
}
sum[0][heavy] = sum[1][heavy] = 0;
Mx[heavy][0] = Mx[heavy][1] = 0;
frp[heavy] = 1;
dfs2(heavy,0);
// for(int u:S) printf("%d Mx[0] %d Mx[1] %d %llu dep %d frp %d\n",u,Mx[u][0],Mx[u][1],sum[1][u],dep[u],frp[u]);
ans = 0;
for(int u:S) add(u);
answer += ans;
buc[0].clear();buc[1].clear();buc[2].clear();
// printf("%lld\n",answer);
ans = 0;
for(int i = head[heavy];i;i = edge[i].nxt){
if(vis[edge[i].to]) continue;
dfs4(edge[i].to,heavy);
buc[0].clear();buc[1].clear();buc[2].clear();
}
answer -= ans;
// printf("%lld\n",answer);
for(int u:S){
inq[u] = 0;
G[u].clear();
}
vis[heavy] = 1;
for(int i = head[heavy];i;i = edge[i].nxt) if(!vis[edge[i].to]) solve(edge[i].to);
}
int main(){
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
dep[0] = -1;
scanf("%d",&n);
rep(u,2,n){
scanf("%d",&fa[u]);
make(fa[u],u);
make(u,fa[u]);
}
rep(u,1,n) a[u] = rnd();
// rep(u,1,n) printf("%llu ",a[u]);
// printf("\n");
rep(u,2,n) scanf("%d",&fa[u]);
solve(1);
printf("%lld\n",answer + n);
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 631ms
memory: 27636kb
input:
5000 1296 1400 867 4533 1296 2007 2059 115 821 2960 3187 1597 2409 2708 4743 4778 1345 3967 911 3400 4249 3793 339 3145 3490 607 4148 3513 3264 3852 568 775 828 1348 423 3678 305 1938 1096 1373 2662 1048 4328 4208 203 779 3103 3372 4523 192 264 792 4943 2211 2494 3513 3555 4935 3277 3390 4624 128 18...
output:
75544
result:
wrong answer 1st numbers differ - expected: '76002', found: '75544'
Subtask #2:
score: 0
Time Limit Exceeded
Test #6:
score: 0
Time Limit Exceeded
input:
200000 13177 40498 104798 83659 186055 32788 86489 72123 13521 134868 158968 60124 166316 163390 120935 103000 83938 57807 97940 40447 137723 154683 191864 59080 102808 3969 21451 165592 128776 49468 4101 26441 139317 59503 18053 118809 187783 149816 21609 98521 165692 52964 60425 23437 29614 106886...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%