精华内容
下载资源
问答
  • 给定彼此独立的两棵树头节点分别为 t1 和 t2,判断 t1 中是否有与 t2 树拓扑结构完全相同 的子树。 例如,如图3-36 所示的 t1 树和如图 3-37 所示的 t2 树。 题解 如果 t1 的节点数为 N,t2 的节点数为 M,则本题最...

    本题来自左神《程序员代码面试指南》“判断 t1 树中是否有与 t2 树拓扑结构完全相同的子树”题目。

    题目

    给定彼此独立的两棵树头节点分别为 t1 和 t2,判断 t1 中是否有与 t2 树拓扑结构完全相同
    的子树。
    例如,如图3-36 所示的 t1 树和如图 3-37 所示的 t2 树。

    在这里插入图片描述

    题解

    如果 t1 的节点数为 N,t2 的节点数为 M,则本题最优解是时间复杂度为O(N+M)的方法。

    首先简单介绍一个时间复杂度为O(N×M)的方法:

    对于 t1 的每棵子树,都去判断是否与 t2 树的拓扑结构完全一样,这个过程的时间复杂度为O(M),t1 的子树一共有 N 棵,所以时间复杂度为O(N×M),这种方法在本文中不再详述。

    下面重点介绍一下时间复杂度为O(N+M)的方法:

    首先把 t1 树和 t2 树按照先序遍历的方式序列化,关于这个内容,请阅读“二叉树的序列化和反序列化”问题。以题目的例子来说,t1 树序列化后的结果为“1!2!4!#!8!#!#!5!9!#!#!#!3!6!#!#!7!#!#!”,记为t1Str。t2 树序列化后的结果为“2!4!#!8!#!#!5!9!#!#!#!”,记为 t2Str。

    接下来,只要验证 t2Str 是否是 t1Str 的子串即可,这个用 KMP 算法可以在线性时间内解决

    因此,t1 序列化的过程为 O(N),t2 序列化的过程为 O(M),KMP 解决 t1Str 和 t2Str 的匹配问题 O(M+N),所以时间复杂度为 O(M+N)。

    有关 KMP 算法的内容,请读者阅读“KMP 算法”问题,关于这个算法非常清晰的解释,这里不再详述。

    代码

    含测试用例

    package chapter_3_binarytreeproblem;
    
    public class Problem_12_T1SubtreeEqualsT2 {
    
        public static class Node {
            public int value;
            public Node left;
            public Node right;
    
            public Node(int data) {
                this.value = data;
            }
        }
    
        public static boolean isSubtree(Node t1, Node t2) {
            String t1Str = serialByPre(t1);
            String t2Str = serialByPre(t2);
            return getIndexOf(t1Str, t2Str) != -1;
        }
    
        public static String serialByPre(Node head) {
            if (head == null) {
                return "#!";
            }
            String res = head.value + "!";
            res += serialByPre(head.left);
            res += serialByPre(head.right);
            return res;
        }
    
        // KMP
        public static int getIndexOf(String s, String m) {
            if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
                return -1;
            }
            char[] ss = s.toCharArray();
            char[] ms = m.toCharArray();
            int[] nextArr = getNextArray(ms);
            int index = 0;
            int mi = 0;
            while (index < ss.length && mi < ms.length) {
                if (ss[index] == ms[mi]) {
                    index++;
                    mi++;
                } else if (nextArr[mi] == -1) {
                    index++;
                } else {
                    mi = nextArr[mi];
                }
            }
            return mi == ms.length ? index - mi : -1;
        }
    
        public static int[] getNextArray(char[] ms) {
            if (ms.length == 1) {
                return new int[]{-1};
            }
            int[] nextArr = new int[ms.length];
            nextArr[0] = -1;
            nextArr[1] = 0;
            int pos = 2;
            int cn = 0;
            while (pos < nextArr.length) {
                if (ms[pos - 1] == ms[cn]) {
                    nextArr[pos++] = ++cn;
                } else if (cn > 0) {
                    cn = nextArr[cn];
                } else {
                    nextArr[pos++] = 0;
                }
            }
            return nextArr;
        }
    
        public static void main(String[] args) {
            Node t1 = new Node(1);
            t1.left = new Node(2);
            t1.right = new Node(3);
            t1.left.left = new Node(4);
            t1.left.right = new Node(5);
            t1.right.left = new Node(6);
            t1.right.right = new Node(7);
            t1.left.left.right = new Node(8);
            t1.left.right.left = new Node(9);
    
            Node t2 = new Node(2);
            t2.left = new Node(4);
            t2.left.right = new Node(8);
            t2.right = new Node(5);
            t2.right.left = new Node(9);
    
            System.out.println(isSubtree(t1, t2));
    
        }
    
    }
    
    
    展开全文
  • 那么在第二棵树上的两点u′,v′u',v'u′,v′的距离就是两棵树上距离总和-u,vu,vu,v在第一棵树上的lcalcalca的深度×2\times 2×2 考虑枚举这个lcalcalca,那么答案就应该是lcalcalca的两个不同子树S1,S2S1,S...

    题目
    先考虑两棵树怎么做。
    我们在第二棵树的每一个点uu上再挂一个点uu',他们的距离为第一棵树上的depudep_u
    那么在第二棵树上的两点u,vu',v'的距离就是两棵树上距离总和-u,vu,v在第一棵树上的lcalca的深度×2\times 2
    考虑枚举这个lcalca,那么答案就应该是lcalca的两个不同子树S1,S2S1,S2,求uS1,vS2u'\in S1,v'\in S2的在第二棵树上的dis(u,v)dis(u',v')的最大值-lcalca的深度×2\times 2
    两个点集间的最长距离的两个端点一定可以是在两个点集各自的直径端点中各取一个。
    所以就动态维护点集直径即可,
    时间复杂度O(nlogn)O(n\log n)
    如果O(1)LCAO(1)LCA的话就是预处理O(nlogn)O(n\log n)解答O(n)O(n)

    再加入一颗树。
    那么在第三颗树上边分治,把一个点集SS分成两个集合S1,S2S1,S2
    那么我们在第一棵树上建立点集SS的虚树,
    然后对于第一棵树和第二棵树我们用之前的做法不过现在我们要更新答案,
    两个端点不能同在S1S1或同在S2S2
    简单DPDP一下即可。
    时间复杂度O(nlognsort(n)+nlogn)O(n\log n * sort(n) + n\log n)
    用基排好像可以O(nlogn)O(n\log n)的理性愉悦一下。

    我居然只是小小的调了几个错而已。
    这代码比紫荆花之恋和希望都长,应该是我目前最长的代码了

    AC Code\mathrm {AC \ Code}

    #include<bits/stdc++.h>
    #define maxn 400005
    #define LL long long
    #define Ct const
    #define lim 19
    #define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)
    #define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--)
    #define ADJ(i,u) for(int i=info[u],v;i;i=Prev[i])
    using namespace std;
    
    char cb[1<<16],*cs=cb,*ct=cb;
    #define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<16,stdin),cs==ct)?0:*cs++)
    template<class T>void read(T &res){char ch;for(;!isdigit(ch=getc()););for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0');}
    
    int n,lg[maxn];
    LL ans;
    
    void PrePare_ST(int MN[lim][maxn],int *dep,int n){ rep(j,1,lim-1)rep(i,0,n-(1<<j)+1)MN[j][i]=dep[MN[j-1][i]]<dep[MN[j-1][i+(1<<j-1)]]?MN[j-1][i]:MN[j-1][i+(1<<j-1)];  }
    namespace Tree1{
    	int info[maxn],Prev[maxn<<1],to[maxn<<1],cnt_e;
    	LL dep[maxn],cst[maxn<<1],adep[maxn];
    	int MN[lim][maxn],ptdep[maxn],st[maxn],dfn;
    	void Node(int u,int v,LL w){ Prev[++cnt_e]=info[u],info[u]=cnt_e,to[cnt_e]=v,cst[cnt_e]=w; }
    	void dfs(int u,int ff){
    		MN[0][st[u] = ++dfn]=u;
    		ADJ(i,u) if((v=to[i])^ff) dep[v]=dep[u]+cst[i],ptdep[v]=ptdep[u]+1,dfs(v,u),MN[0][++dfn]=u;
    	}
    	void init(){
    		int u,v;LL w;
    		rep(i,1,n-1) read(u),read(v),read(w),Node(u,v,w),Node(v,u,w);
    	}
    	int LCA(int u,int v){
    		u = st[u] , v = st[v];
    		if(u > v) swap(u,v);
    		int t = lg[v-u+1];
    		return ptdep[MN[t][u]]<ptdep[MN[t][v-(1<<t)+1]]?MN[t][u]:MN[t][v-(1<<t)+1];
    	}
    	LL dis(int u,int v){ if(!u || !v) return 0;u+=n,v+=n; return adep[u] + adep[v] + dep[u] + dep[v] - 2 * dep[LCA(u,v)]; }
    }
    using Tree1::dis;
    int ar[maxn];
    namespace Tree2{
    	int info[maxn],Prev[maxn<<1],to[maxn<<1],cnt_e;
    	LL dep[maxn],cst[maxn<<1];
    	int MN[lim][maxn],ptdep[maxn],st[maxn],col[maxn],dfn;
    	void Node(int u,int v,LL w){ Prev[++cnt_e]=info[u],info[u]=cnt_e,to[cnt_e]=v,cst[cnt_e]=w; }
    	void dfs(int u,int ff){
    		MN[0][st[u] = ++dfn]=u;Tree1::Node(u,u+n,dep[u]);
    		ADJ(i,u) if((v=to[i])^ff) dep[v]=dep[u]+cst[i],ptdep[v]=ptdep[u]+1,dfs(v,u),MN[0][++dfn]=u;
    	}
    	void init(){
    		int u,v;LL w;
    		rep(i,1,n-1) read(u),read(v),read(w),Node(u,v,w),Node(v,u,w);
    		dfs(1,0);
    		PrePare_ST(MN,ptdep,dfn);
    		Tree1::dfs(1,0);
    		PrePare_ST(Tree1::MN,Tree1::ptdep,Tree1::dfn);
    	}
    	int LCA(int u,int v){
    		u = st[u] , v = st[v];
    		if(u > v) swap(u,v);
    		int t = lg[v-u+1];
    		return ptdep[MN[t][u]]<ptdep[MN[t][v-(1<<t)+1]]?MN[t][u]:MN[t][v-(1<<t)+1];
    	}
    	bool cmp(Ct int &u,Ct int &v){ return st[u]<st[v]; }
    	int f[maxn][2][2];
    	void merge(int u,int v){
    		rep(i,0,1) rep(j,0,1) rep(k,0,1)ans = max(ans , dis(f[u][i][j],f[v][i^1][k]) - 2 * dep[u]);
    		rep(i,0,1){
    			int a=f[u][i][0],b=f[u][i][1];LL d=dis(a,b),t;
    			rep(j,0,1) rep(k,0,1) if((t=dis(f[u][i][j],f[v][i][k]))>d || (!a && !b))
    				d=t,a=f[u][i][j],b=f[v][i][k];
    			if((t=dis(f[v][i][0],f[v][i][1]))>d || (!a && !b))
    				d=t,a=f[v][i][0],b=f[v][i][1];
    			f[u][i][0]=a,f[u][i][1]=b;
    		}
    	}
    	void newnode(int u){  
    		if(!col[u]) f[u][0][0] = f[u][0][1] = f[u][1][0] = f[u][1][1] = 0;
    		if(col[u] == 1) f[u][0][0] = f[u][0][1] = u , f[u][1][0] = f[u][1][1] = 0;
    		if(col[u] == 2) f[u][0][0] = f[u][0][1] = 0 , f[u][1][0] = f[u][1][1] = u;
    	}
    	void Solve(){
    		sort(ar+1,ar+1+ar[0],cmp);
    		static int q[maxn],R=0;
    		rep(i,1,ar[0]){
    			if(R){
    				int t=LCA(q[R],ar[i]),p=0;
    				for(;R&&ptdep[q[R]]>ptdep[t];p=q[R--]) if(p) merge(q[R],p);
    				if(q[R]^t) q[++R]=t,newnode(t);
    				if(p) merge(q[R],p);
    			}
    			q[++R]=ar[i],newnode(ar[i]);
    		} 
    		for(int p=0;R;p=q[R--])
    			if(p) merge(q[R],p);
    	}
    }
    namespace Tree3{
    	int info[maxn],Prev[maxn<<1],to[maxn<<1],cnt_e;
    	LL dep[maxn],cst[maxn<<1],cts[maxn<<1];
    	void Node(int u,int v,LL w){ Prev[++cnt_e]=info[u],info[u]=cnt_e,to[cnt_e]=v,cst[cnt_e]=w; }
    	int fir[maxn],tar[maxn<<1],nxt[maxn<<1],cnte=1;
    	void add(int u,int v,LL w=0){ nxt[++cnte]=fir[u],fir[u]=cnte,tar[cnte]=v,cts[cnte]=w; }
    	void lin(int u,int v,LL w=0){ add(u,v,w),add(v,u,w); }
    	int N,sz[maxn];bool vis[maxn];
    	void Build(int u,int ff){
    		int p=0;
    		ADJ(i,u) if((v=to[i])^ff) Build(v,u),++N,p&&(lin(N,p),0),lin(p=N,v,cst[i]);
    		if(p) lin(u,p);
    	}
    	void dfs(int u,int ff,int tsz,int &mn,int &rt){
    		sz[u] = 1;
    		for(int i=fir[u],v;i;i=nxt[i]) if((v=tar[i])^ff && !vis[i]){
    			dfs(v,u,tsz,mn,rt),sz[u]+=sz[v];
    			if(max(sz[v],tsz-sz[v]) < mn)
    				mn = max(sz[v] , tsz-sz[v]) , rt = i;
    		}
    	}
    	int Gert(int u,int tsz){
    		static int mn,rt;
    		dfs(u,0,tsz,mn=0x3f3f3f3f,rt=-1);
    		return rt;
    	}
    	void ser(int u,int ff,LL d,int tp){
    		if(u<=n)
    			Tree1::adep[u+n] = d,
    			ar[++ar[0]] = u;
    		Tree2::col[u] = tp;
    		sz[u] = 1;
    		for(int i=fir[u],v;i;i=nxt[i])
    		 if((v=tar[i])^ff && !vis[i]) ser(v,u,d+cts[i],tp),sz[u]+=sz[v];
    	}
    	void Solve(int u){
    		if(u == -1) return;
    		vis[u] = vis[u^1] = 1;
    		ar[0] = 0;
    		ser(tar[u],0,cts[u],1);
    		ser(tar[u^1],0,0,2);
    		Tree2::Solve();
    		Solve(Gert(tar[u],sz[tar[u]])),Solve(Gert(tar[u^1],sz[tar[u^1]]));
    	}
    	void init(){
    		int u,v;LL w;
    		rep(i,1,n-1) read(u),read(v),read(w),Node(u,v,w),Node(v,u,w);
    		N=n;Build(1,0);
    		Solve(Gert(1,N));
    	}
    }
    
    int main(){
    //	freopen("1.in","r",stdin);
    //	freopen("1.out","w",stdout);
    	rep(i,2,maxn-1) lg[i]=lg[i>>1]+1; 
    	scanf("%d",&n);
    	Tree1::init(),Tree2::init(),Tree3::init();
    	printf("%lld\n",ans);
    }
    
    展开全文
  • 入门

    2017-10-02 23:09:00
    在处理某些问题时,不需要用到整棵树的信息,只需要某些点时,我们可以新建一棵虚树来放这些点与某些关键点。通常来说,构建的虚树中有这些点和这些点的lca。假如我们要将k个点与其lca构成一棵虚树,那么所需要的...

    虚树入门

    标签: 虚树


    概念

    在处理某些问题时,不需要用到整棵树的信息,只需要某些点时,我们可以新建一棵虚树来放这些点与某些关键点。通常来说,构建的虚树中有这些点和这些点的lca。假如我们要将k个点与其lca构成一棵虚树,那么所需要的时间复杂度为O(klogk)。

    顺便提一下,这k个点和其所有的lca的点的个数和是小于2×k-1的,至于为什么的话,可以看构树的过程,每加入一个点最多只会多一个点。

    构建过程

    我们先对原树dfs一遍,得到原树的dfs序。
    然后我们把需要加入的点按照dfs序排序,这有什么好处呢,下文会提到。
    我们还需要维护一个栈,这个栈中存的是最后一个新加入的点的dfs链。(在这条链上,dfs序是递增的)
    现在新插入一个点v,假如栈顶的元素为u,现在有两种情况:

    1. lca(u,v)==u:
      • 我们就可以直接把v插入栈中,继续维护这条链;
    2. lca(u,v)!=u:
      • 首先lca(u,v)不可能等于v吧。(因为我们是按照dfs序依次加入的,这点很重要!)
      • 其次,再也没有新的点会插入在u的子树内了(因为我们是按照dfs序依次加入的,这点很重要!)。
      • 所以这一条链已经没有多大维护的价值了,我们把这一条链加入到虚树中,具体怎么做呢?
      • 假如栈顶为p,栈中的第二个元素为q。
      • 当dfn[q]>dfn[Lca]这时q还在Lca子树内,q->p连边,弹出栈顶。
      • 当dfn[q]==dfn[Lca]这时q为Lca,q->p连边。
      • 当dfn[q]< dfn[Lca]这时元素q还有维护的价值(可以q->Lca->v构成一个新的链),Lca->p连边,弹出栈顶,Lca加入栈。
      • 最后插入v。

    等点全部加完后,记得把栈中的所有点加到虚树里去。(这是初学者容易犯的错误)
    这样一棵虚树就建好了。


    推荐几道模板题:
    [Sdoi 2011]消耗战
    [Heio 2014]大工程

    转载于:https://www.cnblogs.com/gzy-cjoier/p/7622928.html

    展开全文
  • 给定一棵树,求出从哪个点跑最短路使得最短路径的和最小 思路 二次扫描换根法 先用一遍dfsdfsdfs求出一个点的最短路,然后考虑换根带来的最短路影响 以样例为例,假设我们现在要从1换根到2 我们考虑换根会...

    大意

    给定一棵树,求出从哪个点跑最短路使得最短路径的和最小


    思路

    二次扫描换根法

    先用一遍dfsdfs求出一个点的最短路,然后考虑换根带来的最短路影响

    以样例为例,假设我们现在要从1换根到2
    干得漂亮
    我们考虑换根会带来的影响,发现1和3(绿点)多走了2那条边,而2和4少走1(红点)那条边
    无所不有
    这样我们就得到了状态转移方程
    f[y]=f[x]+(nnum[y])×e[i].wnum[y]×e[i1].wf[y]=f[x]+(n-num[y])\times e[i].w-num[y]\times e[i^1].w

    f[]=f[]+××f[儿子] =f[父亲]+父亲其他儿子的子节点数 \times 儿子连向父亲的边-儿子的子节点数\times 父亲连向儿子的边

    通不通俗,易不易懂


    代码

    #pragma GCC optimize(2)
    #include<cstring>
    #include<cstdio>
    #define ri register int
    #define r(i,a,b) for(register int i=a;i<=b;i++)
    using namespace std;const int N=1400001;
    int n,l[N],tot=1,yh[N],x,y,z,ans=1,num[N];
    struct node{int next,to,w;}e[N<<1];
    inline void add(ri u,ri v,ri w){e[++tot]=(node){l[u],v,w};l[u]=tot;return;}
    bool vis[N]={0};
    long long f[N];
    inline int read()//输入优化
    {
    	int f=0,d=1;char c;
    	while(c=getchar(),c<48||c>57)if(c=='-')d=-1;f=(f<<3)+(f<<1)+c-48;
    	while(c=getchar(),c>47&&c<58)f=(f<<3)+(f<<1)+c-48;
    	return d*f;
    }
    inline void write(long long x)//输出优化
    {
    	if(x<0) {x=-x;putchar('-');}
    	if(x>9)write(x/10);putchar(x%10+48);
    	return;
    }
    inline void dfs(ri x)//求单点最短路
    {
    	vis[x]=true;num[x]++;
    	for(register int i=l[x];i;i=e[i].next)
    	{
    		int y=e[i].to;
    		if(!vis[y])
    		{
    			dfs(y);
    			num[x]+=num[y];
    			f[1]+=e[i].w*num[y];
    		}
    	}
    	return;
    }
    inline void dp(ri x)//换根
    {
    	vis[x]=true;
    	for(register int i=l[x];i;i=e[i].next)
    	{
    		int y=e[i].to;
    		if(!vis[y])
    		{
    			f[y]=f[x]+(n-num[y])*(e[i^1].w)-num[y]*(e[i].w);
    			dp(y);
    			if(f[y]<f[ans]) ans=y;
    			if(f[y]==f[ans]) if(y<ans) ans=y;
    		}
    	}
    	return;
    }
    signed main()
    {
    	n=read();
    	r(i,1,n) yh[i]=read();
    	r(i,1,n-1)
    	{
    		x=read();y=read();z=read();
    		add(x,y,z-yh[x]);add(y,x,z-yh[y]);
    	}
    	dfs(1);
    	memset(vis,0,sizeof(vis));
    	dp(1);
    	write(ans);putchar(10);write(f[ans]);//输出
    }
    
    展开全文
  • 和二叉树

    2020-04-30 17:28:10
    树的基本概念 定义 概念(什么是树,什么是子树): 树是递归的 *思考题:n个结点有(n-1)条边 基本术语 (祖先结点和子孙结点,双亲...2,某层的结点数 i层最大节点数=m^(i-1) 这棵树颗m×树 3,总共的结...
  • (tree)

    2018-09-23 15:34:00
    给定一棵nn个节点的上每个点有点权xixi 。 对于一条路径i1,i2,…,ik,定义路径的权值为xi1×xi2×⋯×xik/k 现在要找一条权值最小的路径,请以分数的形式输出路径的权值。   输入   第一行包括一个...
  • 链剖分

    2017-12-18 13:22:50
    主要思路将整棵树的边分为轻边和重边,将每个重边连成的链当作个区间,用维护区间的数据结构去维护它。如何选择重边一般选连接子树所含节点最多的儿子作为重边,如图: 这样可以保证从根节点到任何个节点,...
  • 给出nnn个点的一棵树,每个点有一个权值aia_iai​,求 ∑i=1n∑j=1ndis(i,j)×φ(ai×aj)\sum_{i=1}^n\sum_{j=1}^ndis(i,j)\times \varphi(a_i\times a_j)i=1∑n​j=1∑n​dis(i,j)×φ(ai​×aj​) 2≤n≤2×1052\...
  • 当 K=0K=0K=0,遍历整棵树,每条边必然被递归依次,回溯次,故路线总长度为 2×(n−1)2\times (n-1)2×(n−1)。 当 K=1K=1K=1,由于新增的边必须正好经过次,那么由于新增边而构成的环需要遍历次,则环上的树...
  • Luogu5889 跳

    2021-01-30 14:20:32
    一天,兔子在一棵点数为 2n−12^n-12n−1 完全二叉上的一个结点上,他准备进行若干次如下的跳跃。 跳到这个点的左儿子,保证这个点有左儿子。 跳到这个点的右儿子,保证这个点有右儿子。 跳到这个点的父亲,若这...
  • 一棵树,Q次询问颜色在[L,R]之间的点到x的距离之和,强制在线 n≤1.5×105,Q≤2×105n\le1.5\times10^5,Q\le2\times10^5n≤1.5×105,Q≤2×105 Solution 带修改的话就是树套树,这里不用修改就可持久化就好了 说...
  • 一棵 n 个结点,根为结点 1 的,每个结点有一个选取代价 aia_iai​,当前 bib_ibi​(0或1),目标数字 cic_ici​(0或1) 。每次可以选择以一个结点为根节点的子树中的 k 个结点,然后任意分配它们的 bib_ibi​,...
  • 洛谷6374 上询问

    2021-01-24 20:30:25
    给定一棵 n 个点的无根树,有 q 次询问。 每次询问给一个参数三元组 (a,b,c) ,求有多少个 i 满足这棵树在以 i 为根的情况下 a 和 b 的 LCA 为 c 。 数据范围 对于所有数据:1≤n≤5×1051 \leq n \leq 5\times10^{5...
  • bzoj1564 二叉查找

    2017-01-09 16:30:00
    只有个数字,即你所能得到的整棵树的访问代价与额外修改代价之和的最小值。 Sample Input 4 10 1 2 3 4 1 2 3 4 1 2 3 4 Sample Output 29 HINT 输入的原图是左图,它的访问代价是1×1+2×2+3×3+4...
  • 上最短路

    2019-09-27 20:12:11
     给出一棵树进行如下操作:  (1)把某个点上染黑  (2)询问某个点,到最近黑点的距离。  开始时,把‘1’点染黑。  • 10% N,M ≤ 10 • 40% N,M ≤ 100 • 100% N ≤ 2 × 10 5 ,M ≤ 10 5 思路:...
  • 其中区域树就是一种正交查找的常用方法,主要思路是将点沿X坐标建立一棵树,再将每个节点的子树按照Y坐标再建立一棵树,具体实现与查找见下文。 二、区域树构建(Build) 首先对于平面中的四个点,可以根据...
  • 一棵树上有n个节点,编号分别为1到 n,每个节点都有一个权值w。 我们将以下面有q个询问,要求你对这棵树完成一些操作: CHANGE u t : 把结点 u 的权值改为 t。 QMAX u v: 询问从点 u 到点 v 的路径上的节点的最大...
  • 一棵树中找出无序点对(a,b)(a,b)(a,b),使aaa和bbb的距离为2,问∑wa×wbmod&amp;ThinSpace;&amp;ThinSpace;10007\sum w_a\times w_b\mod10007∑wa​×wb​mod10007以及max(w[a]×w[b])max(w[a]\times w[b...
  • 浅谈权值线段

    千次阅读 2017-08-08 21:31:08
    我们线段是以标号为关键字的线段,顾名思义,权值线段就是以权值为关键字的一棵线段。其实在实现的时候,比线段还简单,如果你真正理解了线段的话~~权值线段一般是用来快速求一个区间的第k大(或小)...
  • 给定一棵 nnn 个节点的,以及 mmm 条链,每条链有费用,每条边有收益。问选出两条至少一条边重合的链,使链并上的边权和 −-− 两条链的总费用最大。 n≤106,m≤2×106n \le 10^6,m\le 2 \times 10^6n≤106,m≤2×...
  • 5077. 的难题

    2017-04-23 09:42:17
    给定一棵n个点的,每条边有一种颜色,对于一条路径,可以写出一个颜色序列,将颜色序列划分成很多相同颜色的颜色段,定义一条路径的权值是颜色序列的颜色段数。 求中经过边数在l,r之间的路径的最大权值。 Data...
  • 只有个数字,即你所能得到的整棵树的访问代价与额外修改代价之和的最小值。 Sample Input 4 10 1 2 3 4 1 2 3 4 1 2 3 4 Sample Output 29 HINT 输入的原图是左图,它的访问代价是1×1+2×2+3...
  • 20ZR暑期集训 形 dp

    2020-07-22 20:19:06
    HDU 6035 Colorful Tree 给定一棵 nnn 个点的,每个点都有颜色 cic_ici​。定义两点间距离为路径上不同颜色的...一棵大小为 nnn 的有 n×(n−1)2\frac{n \times (n-1)}{2}2n×(n−1)​ 条路径。 CF1101D GCD Coun
  • P4492 [HAOI2018]苹果

    2021-02-24 21:29:13
    性质1:一棵树是合法的充要条件是它是一个二叉堆(小根堆)。 性质2:n个点的子树共有n!种形态。 子树内:先选择编号然后有阶乘种形态。j!×(n−ij−1)  ②j!\times \binom{n-i}{j-1}~~②j!×(j−1n−i​)&...
  • 节点个数问题

    2019-10-01 19:42:13
    一棵二叉树的总度数n=度数为0的节点的数量n0×0+度数为1的节点的数量n1×1+度数为2的节点的数量n2×2一棵二叉树的总度数n同时=所有节点个数n0+n1+n2-1由上述两个式子可得n1+2n2=n0+n1+n2-1所以有n0=n2+1。...
  • 给定一棵nnn个点的,支持三种操作: 给的一条路径打上一类标记 删去一类标记 求未经过某个点的所有标记的最大权值。 n,Q≤2×105n,Q\leq 2\times 10^5n,Q≤2×105 【解题思路】 如果我们二分答案,那么问题就...

空空如也

空空如也

1 2 3 4 5 ... 17
收藏数 332
精华内容 132
关键字:

一棵树×2