Palindromes in a Tree CodeForces - 914E
2024-08-27 13:31:47
https://vjudge.net/problem/CodeForces-914E
点分就没一道不卡常的?
卡常记录:
1.把不知道为什么设的(unordered_map)s换成了(int[])s
2.减少一次cal2和clr
#pragma GCC optimize("Ofast")
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;
struct E
{
int to,nxt;
}e[];
int f1[],ne;
int sz[],fx[],d[];ll ans[],ta,an1[];
char ss[];int a[];
bool vis[];
int root,sum;
int lft[];
int s[];
void getroot(int x,int fa)
{
sz[x]=;fx[x]=;
for(int k=f1[x];k;k=e[k].nxt)
if(!vis[e[k].to]&&e[k].to!=fa)
{
getroot(e[k].to,x);
sz[x]+=sz[e[k].to];
fx[x]=max(fx[x],sz[e[k].to]);
}
fx[x]=max(fx[x],sum-sz[x]);
if(fx[x]<fx[root]) root=x;
}
void getsz(int x,int fa)
{
sz[x]=;
for(int k=f1[x];k;k=e[k].nxt)
if(!vis[e[k].to]&&e[k].to!=fa)
{
getsz(e[k].to,x);
sz[x]+=sz[e[k].to];
}
}
void calc(int u,int fa)
{
an1[u]+=s[d[u]^a[root]],ta+=s[d[u]^a[root]];
for(int i=;i<;i++) an1[u]+=s[d[u]^a[root]^lft[i]],ta+=s[d[u]^a[root]^lft[i]];
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to]&&e[k].to!=fa)
calc(e[k].to,u);
}
void addd(int u,int fa)
{
s[d[u]]++;
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to]&&e[k].to!=fa)
{
d[e[k].to]=d[u]^a[e[k].to];
addd(e[k].to,u);
}
}
void deld(int u,int fa)
{
s[d[u]]--;
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to]&&e[k].to!=fa)
deld(e[k].to,u);
}
void cal2(int u,int fa)
{
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to]&&e[k].to!=fa)
{
cal2(e[k].to,u);
an1[u]+=an1[e[k].to];
}
ans[u]+=an1[u];
}
void clr(int u,int fa)
{
an1[u]=;
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to]&&e[k].to!=fa)
clr(e[k].to,u);
}
void solve(int u)
{
d[u]=;vis[u]=;ta=;
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to])
{
d[e[k].to]=a[e[k].to];
addd(e[k].to,u);
}
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to])
{
clr(e[k].to,u);
deld(e[k].to,u);
calc(e[k].to,u);
addd(e[k].to,u);
}
ans[u]+=ta/;ta=;
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to])
deld(e[k].to,u);
s[]++;
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to])
{
calc(e[k].to,u);
cal2(e[k].to,u);
}
s[]--;ans[u]+=ta;
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to])
{
root=;getsz(e[k].to,);sum=sz[e[k].to];
getroot(e[k].to,);solve(root);
}
}
int n;
int main()
{
fx[]=0x3f3f3f3f;
int i,x,y;
lft[]=;
for(i=;i<=;i++) lft[i]=lft[i-]<<;
scanf("%d",&n);
for(i=;i<n;i++)
{
scanf("%d%d",&x,&y);
e[++ne].to=y;e[ne].nxt=f1[x];f1[x]=ne;
e[++ne].to=x;e[ne].nxt=f1[y];f1[y]=ne;
}
scanf("%s",ss+);
for(i=;i<=n;i++) a[i]=lft[ss[i]-'a'];
root=;sum=n;getroot(,);
solve(root);
for(i=;i<=n;i++) printf("%lld ",ans[i]+);
return ;
}
最新文章
- PHP header函数使用大全
- 空的安卓工程添加activity
- js 事件
- 《BI项目笔记》数据源视图设置
- JavaScript parseInt() toString()函数
- Windows的同步I/O和异步I/O
- JSP SQL注入--破法
- textarea 在光标处插入文字
- NativeExcel 读取文件
- 剑指offer-面试题20.顺时针打印矩阵
- FLAG_ACTIVITY_NEW_TASK和SingleInstance的设计思路(多task的应用)
- sublime模式下开启vim并修改esc
- vs提示“当前不会命中断点,源代码与原始版本不同”的一种解决办法
- 一个轻client,多语言支持,去中心化,自己主动负载,可扩展的实时数据写服务的实现方案讨论
- C#基础 大盘点
- 设计模式,Let&#39;s “Go”! (下)
- 简单谈谈DNS的工作原理及实践
- MySQL 的性能(下篇)—— 性能优化方法
- 微信小程序 人脸识别登陆模块
- 混合开发使用Chrome Inspect调试WebView预览手机界面和定位元素
热门文章
- 键盘HOOK显示按键信息
- Cocos Console命令总结
- 计算(!(~+[])+{})[--[~+";";][+[]]*[~+[]] + ~~!+[]]+({}+[])[[~!+[]]*~+[]]
- hdu acm 2191 悼念512汶川大地震遇难同胞——珍惜现在,感恩生活
- UVA-10600(次小生成树)
- C++对象的复制——具有指针成员的类的对象的复制
- UIAlterController 的使用
- Linux学习—退出vi编辑模式
- J2ee的SSM和SSH的小结
- [技术分享]借用UAC完成的提权思路分享