链式前向星+Poj3321

链式前向星+Poj3321

参考博客：https://blog.csdn.net/acdreamers/article/details/16902023

/*
其中edge[i].to表示第i条边的终点,edge[i].next表示与第i条边同起点的下一条边的存储位置,edge[i].w为边权值.
另外还有一个数组head[],它是用来表示以i为起点的第一条边存储的位置,实际上你会发现这里的第一条边存储的位置其实
在以i为起点的所有边的最后输入的那个编号.
head[]数组一般初始化为-1,对于加边的add函数是这样的:
*/

void add(int u,int v,int w)
{
    edge[cnt].w = w;
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

poj3321

题目是简单题，就是我本人和poj不是很合得来。

1.用到的知识点是dfs序+树状数组

2.开vector会tle，改链式前向星，忘了怎么写，见上面。

3.我的O(n)建BIT数组被卡了，tle

#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define debug(x) cout<<#x<<':'<G[maxn];
struct node {
    int to,nxt;
}edge[maxn<<2];
int tot=0,head[maxn];
void addedge(int u,int v){
    ++tot;
    edge[tot].to=v;
    edge[tot].nxt=head[u];
    head[u]=tot;
}
long long  a[maxn],t[maxn];
namespace BIT
{
    long long lowbit(long long  x){return x&-x;}
    // void init(long long N)//tricks,o(n)建树// 这个时候把n的大小传进来
    // {
    //    // n=N;
    //    // memset(t,0,sizeof(t));
    //     for(long long i=1;i<=n;i++){
    //         t[i]+=a[i];
    //         int j=i+lowbit(i);//向它最近的父亲更新
    //         if(j<=n)t[j]+=t[i];
    //     }
    // }
    void add(long long  x,long long k)//x位置加k
    {
        //a[x]+=k;
        while(x<=n){
            t[x]+=k;
            x+=lowbit(x);
        }
    }
    long long  getsum(long long l,long long r) //闭区间使用[l,r],区间和
    {
        l--;
        long long ansl=0,ansr=0;
        while(l)
        {
            ansl+=t[l];
            l-=lowbit(l);
        }
        while(r)
        {
            ansr+=t[r];
            r-=lowbit(r);
        }
        return ansr-ansl;
    }
}using namespace BIT;
int ls[maxn],rs[maxn],cnt;
void dfs(int root,int b){
    ls[root]=++cnt;
    for(int i=head[root];i!=-1;i=edge[i].nxt){
        if(edge[i].to==b) continue;
        dfs(edge[i].to,root);
    }
    rs[root]=cnt;
}

int main(){
    int cnt=0;
    memset(head,-1,sizeof(head));
    scanf("%d",&n);
    for(int i=1;i
每日一题

相关

【LeetCode每日一题】员工的重要性

【LeetCode每日一题】整数反转

【python】Leetcode每日一题-森林中的兔子

【python】Leetcode每日一题-132模式

【每日一题】【链表】2021年11月20日-141. 环形链表

每日一题-Day31-删除链表的倒数第n个节点

每日一题·暑假 week1

【每日一题】【栈】【递归】【遍历】2021年12月1日-94. 二叉树的中序遍历

# 每日题目-1.6：每日一题+49+50

【每日一题】【list转int数组】【Lambda的简化-方法引用】2022年1月15日-NC45 实现二

【每日一题】【找到位置返回&升序数组中第K大就是n-K小】2022年1月17日-NC88 寻找第K

【每日一题】【map操作】【滑动窗口所需元素】2021年12月22日-76. 最小覆盖子串

标签