网上做衣服的网站有哪些,wordpress关键字回复,建设网站弹出后加载不进去,公司网站如何做维护题目链接
思路#xff1a; 对于一条链可以组成回文串#xff0c;意味着最多只有一个奇数字母#xff0c;比起我们记录路径各个字母的个数和#xff0c;我们可以发现回文串实际上不在意真正的个数#xff0c;只在意个数的奇偶。又我们发现字母只有20来个#xff0c;可以使…题目链接
思路 对于一条链可以组成回文串意味着最多只有一个奇数字母比起我们记录路径各个字母的个数和我们可以发现回文串实际上不在意真正的个数只在意个数的奇偶。又我们发现字母只有20来个可以使用状态压缩那么我们只需要判断压缩后状态里1的个数是否为0或者1. 对于树上的链异或和我们都可以用前缀异或和的思想将x-y的异或和看成v[x]^v[fa[lca]]^v[y]^v[fa[lca]]v表示该点到根的异或和可以发现就等于两个位置的异或和。 对于以x为根的子树里的链只有三种情况 1.不经过根 2.链的一端是根 3.跨过根 容易知道对于第1种情况我们可以看成x子树里的某个子树的情况3所以我们只需要计算每个点的子树里的2,3情况即可。 假如我们遍历到第y个子树前面已经遍历处理完x个子树。我们要处理y和前面x个子树的跨根贡献的话我们不能先将y子树的值处理了因为这可能导致结果是y和y子树里不经过根的链
所以对于每次我们先calc掉x和y的链再add掉y这个子树的内容。 代码
#includebits/stdc.h
using namespace std;
//#define int long long
typedef long long ll;
typedef pairint,int pii;
const int inf0x3f3f3f3f;
const int N5e510;
const int mod1e97;
#define fi first
#define se secondint n,val[N];
vectorint ve[N];
int son[N],siz[N];
int fac[30],mask[N],dep[N];
int ans[N],maxx,vis[(125)];
int flag;
int rtdis;void dfs1(int x,int f){siz[x]1;dep[x]dep[f]1;for(auto y:ve[x]){if(yf) continue;mask[y]^mask[x]; dfs1(y,x);siz[x]siz[y];if(siz[y]siz[son[x]])son[x]y;}
}void calc(int u,int f){if(vis[mask[u]]){maxxmax(maxx,vis[mask[u]]dep[u]-rtdis);}for(int i0;i22;i){if(vis[mask[u]^fac[i]]){maxxmax(maxx,vis[mask[u]^fac[i]]dep[u]-rtdis);}}for(auto v:ve[u]){if(vf||vflag)continue;calc(v,u);}
}void add(int u,int f,int value){if(value1){vis[mask[u]]max(vis[mask[u]],dep[u]);}else{vis[mask[u]]0;}for(auto v:ve[u]){if(vf||vflag)continue;add(v,u,value);}
}
void dfs2(int u,int f,bool keep){for(auto v:ve[u]){if(vf||vson[u])continue;dfs2(v,u,0);ans[u]max(ans[u],ans[v]);//不经过根节点 }if(son[u]){dfs2(son[u],u,1);flagson[u];ans[u]max(ans[u],ans[son[u]]);//不经过根节点 }rtdisdep[u]*2;//根节点的dep两倍方便下面for循环计算跨根的距离 for(auto v:ve[u]){//计算跨根距离disuvdepudepv-2deplcalca就是现在的u if(vf||vflag)continue;calc(v,u);//跨根计算和点分治一样遍历了x个子树现在是y子树先不加y子树的贡献 add(v,u,1);//先计算y到前面x个子树的距离算完再加上y子树的贡献add }//以根为一端 if(vis[mask[u]]){//异或为0 maxxmax(maxx,vis[mask[u]]-dep[u]);}for(int i0;i22;i){//遍历异或和为2的幂 if(vis[mask[u]^fac[i]]){maxxmax(maxx,vis[mask[u]^fac[i]]-dep[u]);}}//前面的add都是从子节点进去的没有跟新到当前节点 vis[mask[u]]max(vis[mask[u]],dep[u]);//同理先不算当前节点的贡献算完这种情况再add flag0; //flag清空是为了下面如果keep0时把整个子树删掉包括这颗子树的重儿子 ans[u]max(maxx,ans[u]);//三种情况都计算完了再更新答案 if(!keep){add(u,f,-1);//add里没有重置maxx和rtdis maxx0;//答案已经存在ans【u】了删除整个子树要重置maxx//maxx不重置在回溯回去更新其他子树不包括当前maxx链的子树答案会可能取不到这个maxx //rtdis0;rtdis可重置可不重置因为用前都重新赋值 }
}
void solve(){cinn;fac[0]1;for(int i1;i23;i)fac[i]fac[i-1]*2;for(int i2;in;i){int a;char b;cinab;ve[a].push_back(i);ve[i].push_back(a);val[i]fac[b-a];mask[i]fac[b-a];}dfs1(1,0);dfs2(1,0,0);for(int i1;in;i)coutans[i] ;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t1;//cint;while(t--){solve();}return 0;
}
