首页 > 其他分享 >Codeforces1778E 【线性基】【换根DP】

Codeforces1778E 【线性基】【换根DP】

时间:2023-02-02 01:44:04浏览次数:56  
标签:xxg int -- maxn kk 线性 Codeforces1778E 换根 DP

我,差30秒,就能AC这道题,我知道错哪的时候是倒计时30,不记得优先级想赌一把,因为我没有先写括号的习惯,所以倒计时14的时候交了,然后想改了括号再交一发,改了括号之后,比赛结束了。

这题很简单,就是你任意选一个点作为根节点,然后你会发现,它给你的\(r\)如果在\(v\)的子树中,其实就相当于砍掉\(v\)对应的那部分子树,我们可以想到一个线性基合并的做法。首先求出子树的线性基,如果\(r\)不在\(v\)的子树中,那么子树的线性基最大值就是答案。否则我们可以找出\(r\)对应的\(v\)的那个儿子。我们用一个线性基记录它父亲砍掉它得到的线性基,然后对它的儿子做一个线性基的前缀和以及线性基的后缀和。对于\(r\)在\(v\)子树中的情况,我们把对应儿子的前缀和和后缀和合并,就可以得到对应线性基的最大值。

代码:

#include<bits/stdc++.h>
using namespace std;

const int maxn = 205000;
const int mod = 998244353;

int n,q;
int a[maxn];
vector<int> g[maxn];
int fa[maxn];

struct query{
    int r,v,ans,flag;
}qy[maxn];
vector<pair<int,int> > pg[maxn];
vector<int> qg[maxn];

int son[maxn];

struct xxg{
    int a[30];
}xr[maxn],xp[maxn],xz[maxn];

xxg merge(xxg alpha,xxg beta){
    for(int i=29;i>=0;i--){
	if(alpha.a[i]){
	    for(int j=i;j>=0;j--){
		if((alpha.a[i]&(1<<j)) == 0) continue;
		if(!beta.a[j]) {beta.a[j] = alpha.a[i];break;}
		else alpha.a[i] ^= beta.a[j];
	    }
	}
    }
    return beta;
}

void dfs(int now,int pa){
    fa[now] = pa; son[now] = 0;
    for(auto x:pg[now]){
	if(son[x.first]){
	    qy[x.second].r = son[x.first];
	    qy[x.second].flag = 1;
	}
    }
    for(int i=0;i<g[now].size();i++){
	if(g[now][i] == pa){
	    swap(g[now][i],g[now][g[now].size()-1]);
	    g[now].pop_back();
	    i--;continue;
	}
	son[now] = g[now][i];
	dfs(g[now][i],now);
    }
    son[now] = 0;
}

void dfs2(int now){
    for(int i=0;i<g[now].size();i++){
	dfs2(g[now][i]);
	xr[now] = merge(xr[now],xr[g[now][i]]);
    }
    int kk = a[now];
    for(int j=29;j>=0;j--){
	if(!(kk & (1<<j))) continue;
	if(!xr[now].a[j]) {xr[now].a[j] = kk;break;}
	else kk ^= xr[now].a[j];
    }
    kk = 0;
    for(int j=29;j>=0;j--){
	if(!(kk & (1<<j)))
	    kk ^= xr[now].a[j];
    }
    for(auto x:pg[now]){
	qy[x.second].ans = kk;
    }
}

void dfs3(int now,xxg xnow){
    int kk = a[now];
    for(int j=29;j>=0;j--){
	if(!(kk & (1<<j))) continue;
	if(!xnow.a[j]) {xnow.a[j] = kk;break;}
	else kk ^= xnow.a[j];
    }
    xxg pri = xnow;
    for(int i=0;i<g[now].size();i++){
	xp[g[now][i]] = pri;
	pri = merge(pri,xr[g[now][i]]);
    }
    pri = xnow;
    for(int i=g[now].size()-1;i>=0;i--){
	xz[g[now][i]] = pri;
	pri = merge(pri,xr[g[now][i]]);
    }
    for(int i=0;i<g[now].size();i++){
	pri = merge(xp[g[now][i]],xz[g[now][i]]);
	kk = 0;
	for(int j=29;j>=0;j--){
	    if(!(kk & (1<<j)))
		kk ^= pri.a[j];
	}
	for(auto x:qg[g[now][i]]){
	    qy[x].ans = kk;
	}
	dfs3(g[now][i],pri);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t; cin>>t;
    while(t--){
	cin >> n;
	for(int i=1;i<=n;i++) fa[i] = 0,g[i].clear();
	for(int i=1;i<=n;i++) pg[i].clear(),qg[i].clear();
	for(int i=1;i<=n;i++) for(int j=29;j>=0;j--) xr[i].a[j]=xp[i].a[j]=xz[i].a[j]=0;
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<n;i++){
	    int u,v; cin >> u >> v;
	    g[u].push_back(v);
	    g[v].push_back(u);
	}
	cin >> q;
	for(int i=1;i<=q;i++){
	    int r,v; cin >> r >> v;
	    if(r == v) r = v = 1;
	    qy[i] = (query){r,v,0,0};
	    pg[r].push_back(make_pair(v,i));
	}
	dfs(1,0);
	for(int i=1;i<=n;i++) pg[i].clear();
	for(int i=1;i<=q;i++){
	    if(qy[i].flag == 0) {qy[i].r = qy[i].v;
		pg[qy[i].v].push_back(make_pair(qy[i].r,i));
	    }else{
		qg[qy[i].r].push_back(i);
	    }
	}
	dfs2(1);
	xxg emp;
	memset(emp.a,0,sizeof(emp.a));
	dfs3(1,emp);
	for(int i=1;i<=q;i++){
	    cout<<qy[i].ans<<'\n';
	}
    }
    
}

标签:xxg,int,--,maxn,kk,线性,Codeforces1778E,换根,DP
From: https://www.cnblogs.com/Menhera/p/17084631.html

相关文章

  • C/C++ Socket UDP 广播消息的发送与接收
    C/C++SocketUDP广播消息的发送与接收局域网内全网段广播消息的IP地址为:255.255.255.255,向该IP地址发送广播消息,局域网下的任何网段的客户机都能收到广播。对于发送端,如果......
  • 利用natapp实现TCP、UDP内网穿透
    利用natapp实现TCP、UDP内网穿透natapp官网:​​https://natapp.cn/​​下载:下载下来其实就只有一个文件:首先在natapp官网上注册一个账号,并实名认证,这一步是必须的!然后去购买......
  • Ubuntu错误:E: Could not open lock file /var/lib/dpkg/lock-frontend
    Ubuntu错误:E:Couldnotopenlockfile/var/lib/dpkg/lock-frontendubuntu使用apt下载和更新软件的时候,出现了以下错误:E:Couldnotopenlockfile/var/lib/dpkg/lock-f......
  • 数位DP
    一、常见题面求两个数之间的满足特定条件的数的方案数(提高+/省选-位数为\(10^6\);省选/NOI-位数为\(10^{18}\)or有一些奇奇怪怪的操作)例子:待完善求两个数之间......
  • ThreadPoolExecutor线程池参数设置技巧
    一、ThreadPoolExecutor的重要参数1、corePoolSize:核心线程数*核心线程会一直存活,及时没有任务需要执行*当线程数小于核心线程数时,即使有线程空闲,线程池也会优先创建......
  • JavaFX 网格布局 GridPane
    packagefx.com;importjavafx.application.Application;importjavafx.scene.Scene;importjavafx.scene.control.Button;importjavafx.scene.image.Image;importjavafx.......
  • 【YBT2023寒假Day3 A】千与千寻(期望DP)(高斯消元)
    千与千寻题目链接:YBT2023寒假Day3A题目大意一个n*m的平面,你要从(0,0)走到(x,y),你等概率的向上或向右走,然后当你走到(n-1,i)再往右走,就是(0,i),走到(i,m-1)再......
  • AT dp 26 题 题解
    题单:https://www.luogu.com.cn/training/100578#problems嘛虽然是26题,但是简单的题就不想写了...就写绿题及以上的吧目录EIJMOPQRSTUVE对重量dp,设\(dp[i][v]\)表......
  • NAPT网络结构下TCP/UDP/ICMP访问外网原理思考
    背景作为程序员,应该都听说过NAT(NetworkAddressTransfer,网络地址转换)这一技术名词,并或多或少大概知道其原理与作用--NAT是用于解决IPv4地址不够用,保证我们能够在IPv6普......
  • hdu:Two Rabbits(区间DP)
    ProblemDescriptionLonglongago,therelivedtworabbitsTomandJerryintheforest.Onasunnyafternoon,theyplannedtoplayagamewithsomestones.Th......